[8주차_월요일] 방화벽 설치하기

[baexxbin]

• 사이트 : 코드트리(CT)
• 문제: 방화벽 설치하기
• 년도: 2017

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 3≤ n, m ≤8 → 완전 탐색, 백 트래킹 가능
• DFS + 백 트래킹과 BFS

💡 풀이 아이디어

• 매 진행마다 빈 영역을 이중 반복문으로 계산하면 효율적이지 못하므로 빈 영역을 미리 계산
• DFS로 방화벽을 3개 설치
• 방화벽 설치가 끝났다면 BFS로 불이 번지는 것을 구현
• BFS를 진행하면서 불이 붙는 수를 빈 영역 빼주고 최댓값 갱신
• BFS가 완료 되었다면 방화벽 설치를 백 트래킹을 하여 모든 경우의 수를 구해줌

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : 3<= n, m <=8, O(N * M^3)

💡 풀이 아이디어

• 방화벽 3개를 추가로 설치 했을 때 방화벽을 제외하고 불이 퍼지지 않는 영역 크기의 최댓값을 출력
• 방화벽 3개 추가 설치 : DFS
• 불이 퍼지는 영역 : BFS (Queue),
  • board[i][j]==2 -> 상하좌우 불 번짐, Queue.add(new Node(i, j)
• 불이 번지지않은 영역 : safe()
  • board[i][j]==0, safe++ -> max값 갱신

[baexxbin]

🤔 시간복잡도 고려사항

• 3≤ n, m ≤8
• 완전탐색, 백트래킹 가능 (O(N^2))

💡 풀이 아이디어

• 방화벽 설치 위치 구하기 : 백트래킹(dfs)
• 방화벽 3개 다 설치하면 불 번지기 : bfs
• 모든 불이 다 번지고 난 후 불이 번지지 않은 부분 구하기

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DFS, BFS
• 시간복잡도: 3≤ n, m ≤8 방화벽 3 완전탐색 가능 DFS 풀이 O((N*M)^3 ) + BFS 풀이 O(N*M) = O((N*M)^4)

💡 풀이 아이디어

1. 임의로 방화벽 설치 > 백트래킹
2. 불번지게 하기 > BFS
3. 빈칸 체크, 빈곳이 가장 많이 남은 곳 저장
4. 방화벽 없애기

임의의 조합을 만들어서 방화벽을 설치하는 부분에서 백트래킹을 어떻게 사용하면 되는지 알 수 있었어요. 백트래킹 종료조건과 다음 조합을 위해 삭제 기준을 정하는게 어려웠어서 여러 DFS 문제를 풀어봐야겠어요!

[KodaHye]

🤔 시간복잡도 고려사항

• 3 <= 가로, 세로 <= 8
• 2 <= 총 불의 개수 <= 10
• 3 <= 총 빈 칸의 개수

방화벽을 3개 추가했을 때, 불이 가지 않는 곳의 최대 개수 구하기 → 완탐: 조합: 64-2C3 × BFS: 64 × 4 < 1억

💡 풀이 아이디어

• emptyArea: 처음 map에 대한 정보를 입력받을 때, 빈 칸의 수 세기
• 백트래킹을 통해 방화벽이 아니면서 불이 아닌 곳에 방화벽 3개 놓기
• fireArea: 방화벽을 3개 놓았다면 BFS를 통해 불이 번질 수 있는 곳의 개수 세기
• 불이 번질 수 있는 곳의 수를 모두 셌다면, 3개의 방화벽을 추가로 설치했을 때, 불이 번지지 않는 영역의 최대 크기 계산하기
  • result = Math.min(result, emptyArea - 3 - fireArea)

    백트래킹 할 때, 주어진 자원 최대한 활용 잘 하기 ⭐