[Baekjoon, Python] 7576번 : 토마토

도입

백준 단계별 풀기 DFS와 BFS 여섯 번째 문제이다.

 

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

---

백준 7576번 입출력 예제 1, 2, 3, 4, 5

---

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. 전형적인 bfs 문제, 상하좌우 전부를 체크하면서 가야 하기 때문. 

 

2. bfs 함수내에서는 익은 토마토(1)가 있으면 그 주변의 토마토 좌표는 갖고 있는 값에서 1을 더해준다. (1+1). 그리고 주변좌표를 queue에 담아서 다시 한번 실행하게 한다. 이런식으로 bfs를 진행하면 결과적으로 0이 없이, 최종적으로 다 익기 위해 걸리는 날의 값이 찍히게 된다. 이 값이 max값이 된다. 

3. bfs를 돌리는 것은 토마토가 익으면서 이뤄지는 것들에 대한 결과값을 보여준다. 이후, 이 결과값들에 따라서, 출력을 달리해줘야 한다.

 처음에는 matrix를 세팅하는 중, 1과 -1로만 구성 되어있다면, bfs를 굳이 돌리는 과정을 거칠 필요가 없으니까 이부분의 조건을 따로 뺄 예정이 였으나... 틀렸습니다 를 보고는 그냥 전부 bfs를 돌렸다. 다음에 시간이 더 충분하다면, 이런식으로 matrix를 set하는 for문에서 조건문을 하나 더 넣는 것이 시간을 더 단축시킬 수 있지 않을까 생각한다. 하지만...생각지 못한 경우의 수가 있을 것 같기도 하다. 이 부분에 대해서는 추후에 더 해보도록 하겠다.

---

코드

from sys import stdin
from collections import deque

var_M, var_N = map(int, stdin.readline().split())
matrix = []
queue = deque()
var_rtn  = -2

dx=[-1,0,1,0] # 좌  우 
dy=[0,1,0,-1] #   상  하

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

def bfs():
    while queue: # 익은 토마토 만큼
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < var_N and 0 <= ny < var_M and matrix[nx][ny] == 0: # 익지 않은 토마토면
                matrix[nx][ny] = matrix[x][y] + 1   # 익은 토마토로 변경
                queue.append([nx, ny])              # 다음 익은 토마토 좌표
# 익은 토마토 찾기
for i in range(var_N):
    for j in range(var_M):
        if matrix[i][j] == 1:
            queue.append([i, j]) # 익은토마토 좌표 찾아 큐에 넣기

bfs()

bool_cant = False
for i in matrix: # [9,8,7,6,5,4] , [8,7,6,5,4,3], [7,6,5,4,3,2], [6,5,4,3,2,1]
    for j in i:
        if j == 0: # 토마토가 모두 익지 못하는 상황
            bool_cant = True
        var_rtn  = max(var_rtn , j) # 최대값이 1일경우, 모두 익어있음. 

if bool_cant == True: # 전부 익지 못한다면,
    print(-1)
elif var_rtn  == -1:  # 애초에 다 익었다면
    print(0)
else:                 # 다 익기 위해 걸리는 날 수
    print(var_rtn  - 1)

---

마무리

 결과 값을 print하는데 있어서 0, -1을 상수화 시키고 싶었다. python은 동적언어여서 const, final 과 같은 기능을 지원하지 않고, 다른 방법으로 상수화 시키는 방법들이 있었다. Typing 모듈의 Final을 import한다던지, 클래스를 사용하는 방법이라든지.... 다만, 완벽한 상수화가 아니였다.