2차원 행렬로 표현된 숲이 있다고 가정해 보겠습니다. 각 칸은 다음 세 가지 상태 중 하나입니다.
- 0: 빈 칸
- 1: 나무가 있는 칸
- 2: 불타고 있는 나무가 있는 칸
매일, 인접한 칸(상, 하, 좌, 우 — 대각선 제외)에 불타고 있는 나무가 있으면 그 나무에도 불이 붙습니다. 우리가 구해야 할 것은 모든 나무에 불이 붙기까지 걸리는 일수이며, 만약 모든 나무를 태울 수 없다면 -1을 반환해야 합니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
| 1 | 2 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
이 경우 출력은 4가 됩니다.
문제 접근 방법
이 문제는 너비 우선 탐색(BFS)과 유사한 방식으로 해결할 수 있습니다. 불이 붙어 있는 칸들을 매일 기준으로 확장시키면서, 하루가 지날 때마다 새롭게 불이 붙은 칸들을 추적하는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- 정답을 저장할 변수
ans를 0으로 초기화합니다. - 불이 붙어 있는 칸(값이 2)의 좌표를 담을 리스트
twos를 생성합니다. - 행렬 전체를 순회하면서 값이 2인 칸의 좌표 (i, j)를
twos에 추가합니다. twos가 빌 때까지 다음 과정을 반복합니다.- 새로운 리스트
temp를 생성합니다. twos에 있는 각 좌표 (i, j)에 대해 인접한 네 방향 (i+1, j), (i, j+1), (i-1, j), (i, j-1)을 확인합니다.- 해당 좌표가 행렬 범위 안에 있고 값이 1이라면
temp에 추가합니다. temp에 있는 모든 칸의 값을 2로 변경하여 불이 옮겨붙었음을 표시합니다.twos를temp로 갱신하고, 새로 불이 붙은 칸이 있다면ans를 1 증가시킵니다.
- 새로운 리스트
- 마지막으로 행렬에 값이 1인 칸(아직 불이 붙지 않은 나무)이 남아 있는지 개수를 셉니다.
- 남은 나무가 없으면
ans를, 그렇지 않으면 -1을 반환합니다.
구현 예제
이제 위 로직을 파이썬 코드로 구현해 보겠습니다.
class Solution: def solve(self, matrix): ans = 0 twos = [] for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] == 2: twos.append((i, j)) while twos: temp = [] for i, j in twos: for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]: if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == 1: temp.append((x, y)) for i, j in temp: matrix[i][j] = 2 twos = temp ans += 1 if twos else 0 ones = sum(int(matrix[i][j] == 1) for i in range(len(matrix)) for j in range(len(matrix[0]))) return ans if ones == 0 else -1 ob = Solution() matrix = [ [1, 2, 1], [1, 0, 1], [1, 1, 1] ] print(ob.solve(matrix))
입력
matrix = [ [1, 2, 1], [1, 0, 1], [1, 1, 1] ]
출력
4
이 예제에서 불은 중앙 상단의 나무에서 시작해 매일 상하좌우로 번져나가며, 4일 만에 도달 가능한 모든 나무에 불이 붙게 됩니다. 만약 불이 닿을 수 없는 고립된 나무가 존재한다면 함수는 -1을 반환합니다.