[BOJ/BFS] 7569 토마토

7569번: 토마토

---

풀이

from collections import deque

M, N, H = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N*H)]

# 2. BFS 탐색
def BFS(arr, N):

    di = [-1, 0, 1, 0, -N, N]
    dj = [0, 1, 0, -1, 0, 0]

    while queue:
        r, c = queue.popleft()
        for k in range(6):
            ni = r + di[k]
            nj = c + dj[k]
            if not (r + 1) % N and k == 2:
                pass
            elif not r % N and k == 0:
                pass
            elif 0 <= ni < N*H and 0 <= nj < M:
                if not arr[ni][nj]:
                    arr[ni][nj] = arr[r][c] + 1
                    queue.append((ni, nj))

# 3. 정답
def answer(arr):
    maxV = 0
    for i in range(N*H):
        for j in range(M):
            if not arr[i][j]:
                return -1
            if maxV <= arr[i][j]:
                maxV = arr[i][j]
    return maxV - 1

# 1. 모든 1의 위치를 찾아 인큐
queue = deque()
for i in range(N*H):
    for j in range(M):
        if arr[i][j] == 1:
            queue.append((i, j))
BFS(arr, N)
ans = answer(arr)

print(ans)

---

풀이과정

1. 배열을 순회하면서 모든 1의 좌표를 큐에 넣는다.

2. 상하좌우위아래를 탐색하여 0을 채운다.

3. 이때 '다른 박스'로 나누어지는 기준이 되는 행이면 다른 박스에 있는 행을 같은 박스의 상하에 위치해있다고 헷갈리지 않도록 위, 아래 탐색은 pass 해준다.

→ 예를 들어,

'''
5 5 2
1 -1 1 -1 1
0 0 -1 -1 1
0 -1 -1 1 0
0 -1 0 0 1
0 0 1 -1 1
1 -1 -1 -1 -1
0 -1 0 1 1
0 1 0 0 -1
-1 -1 -1 -1 -1
-1 0 0 1 -1
'''

위 테스트 케이스의 경우, 4행 0열의 0의 값이 5행 0열의 1에 의해 2로 바뀐다.

그런데 실제로 4행 0열은 1층 제일 뒷줄 줄에, 5행 0열은 2층 제일 앞 줄에 위치해있으므로 영향을 줄 수 없는 위치다.

그림으로 보면 다음과 같다.

4. 따라서 arr를 박스 별로 나누어준다.

→ 박스 별로 배열을 따로 만들어 실제로 나누는 것이 아니라 탐색 조건을 추가하여 박스가 나누어진 것처럼 처리한다.

• 해당 행이 그 박스의 마지막 행이라면, 아래를 탐색하지 않는다.
  • (r + 1)이 N의 배수라면, k의 2번 (아래 탐색)을 건너뛴다.
• 해당 행이 그 박스의 처음 행이라면, 위를 탐색하지 않는다.
  • r이 N의 배수라면, k의 0번 (위 탐색)을 건너뛴다.

실제로는 모든 박스가 하나의 배열이지만, 박스 하나의 크기를 벗어나면 해당 박스 배열을 벗어난 것 처럼 처리하는 것이다.

 

5. 탐색을 모두 마치면, 최대 일수를 업데이트한다. 이때 만약 안익은 토마토(0)가 하나라도 있다면 -1을 반환한다.

---

관련문제

[BOJ/BFS] 7576 토마토

이 문제는 7576 토마토에서 조금 더 발전시킨 문제다.

따라서 더 자세한 풀이는 7576 풀이를 참고