[Baekjoon, Python] 7569번 : 토마토

도입

백준 단계별 풀기 DFS와 BFS 열한 번째, 마지막 문제이다.

백준 7569번 문제, 입력, 출력 

---

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. BOJ 7576번 문제를 풀었다면, 접근이 매우 쉽다. matrix 2차원을 3차원으로 생각해서 풀면 된다. 마찬가지로 BFS 푼다.  

 

2. visit 배열에 1을 기록해 줌으로써, 해당 토마토가 익었다는 것을 알려주고, 더 이상 접근하지 않게 한다.

 

3. BFS를 돌면서 레이어 레벨이 내려 갈 때 마다, matrix[nz][nx][ny]의 값에 matrix[z][x][y] + 1을 해준다. 여기서 레이어 레벨이란, root 노드를 기준으로 파생 되는 노드 들이 root 노드와 떨어져 있는 간격을 의미한다. root는 레이어 레벨 0이다.

Tree 구조 참고

---

코드

from sys import stdin
from collections import deque

dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

def bfs():
    while queue:
        x, y, z = queue.popleft()
        visit[z][x][y] = 1
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            # 주변이 익지 않았고 방문하지 않았다면,
            if 0 <= nx < var_N and 0 <= ny < var_M and 0 <= nz < var_H and matrix[nz][nx][ny] == 0 and visit[nz][nx][ny] == 0:
                queue.append([nx, ny, nz]) # 큐에 넣고 ( 다음 while문에서 돌리기 위해)
                matrix[nz][nx][ny] = matrix[z][x][y] + 1 # 현재 값 + 1 을 인접칸의 값으로 한다.
                visit[nz][nx][ny] = 1

var_M, var_N, var_H = map(int, stdin.readline().split())
matrix = [[] for i in range(var_H)]
visit = [[[0 for i in range(var_M)] for i in range(var_N)] for i in range(var_H)]

for i in range(var_H):
    for j in range(var_N):
        matrix[i].append(list(map(int, stdin.readline().split())))

queue = deque()
for z in range(var_H):
    for x in range(var_N):
        for y in range(var_M):
            if matrix[z][x][y] == 1:
                queue.append([x, y, z])

bfs()

var_rtn = 0
bool_cant = False
for z in range(var_H):
    for x in range(var_N):
        for y in range(var_M):
            if matrix[z][x][y] == 0:
                bool_cant = True
            var_rtn = max(var_rtn, matrix[z][x][y])
if bool_cant == True:
    print(-1)
else:
    print(var_rtn - 1)

---

마무리

이것으로 DFS&BFS 문제를 마치겠다.