[Python][백준/BOJ] 7576번 : 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

내 코드

import sys
input = sys.stdin.readline
from collections import deque

dx = [0,0,1,-1]
dy = [1,-1,0,0]
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
q= deque()

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i,j))

def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            
            if 0<=nx < n and 0<=ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] +1
                    q.append((nx, ny))
bfs()
flag =0
ans =0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            flag =1
            break
if flag:
    print('-1')
else:
    print(max(map(max, graph))-1)

 

코드 리뷰

BFS

처음 문제를 이해할 때 어려움이 있었다. 처음 문제를 이해했을 때는 1을 둘러싸고 있는 0의 층별로 수가 하나씩 증가하는 형태인 줄 알았다. 하지만 1에서 시작해서 숫자 하나하나씩 증가하면 되는 방법이었다. (기존 BFS랑 크게 다를 것이 없었다.)

이 문제의 난이도를 높인 부분은 1인 지점을 찾아서 queue에 넣고 시작한다는 점이 아닐까 싶다. 일반적인 BFS 문제들과 다른 부분은 바로 여기였기 때문이다. 

 

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i,j))

1인 부분을 모조리 다 q에 넣어주면 된다.

 

def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            
            if 0<=nx < n and 0<=ny < m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] +1
                    q.append((nx, ny))

bfs 함수에서는 q에 값이 있을 동안 계속 계산을 반복한다. 처음에 q에 있는 값은 1이 있는 좌표이므로, 1이 있는 좌표에서 출발한다고 생각하면 된다. 그래서 그 옆에 있는 0을 발견한다면 현재 자리의 그래프 값에 1씩 더한 수를 저장한다. 그리고 0이었던 자리를 지나갔다면, 익은 토마토가 되었다고 생각할 수 있다. 익은 토마토는 익지 않은 토마토에 영향을 줄 수 있으므로, q에 익은 토마토의 자리를 저장한다.

 

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            flag =1
            break
if flag:
    print('-1')
else:
    print(max(map(max, graph))-1)

 bfs를 다 돌고 그래프를 다시 한바퀴 전체적으로 돌면서 0이 있는지 확인한다. 만약 0이 아직도 남아있다면 -1과 -1 사이에 0이 가려져있어서 익지 못했으므로 -1을 출력한다.

그리고 토마토가 다 익었다면, 그래프에서 가장 큰 값을 출력한다. 하루에 한 개씩 익는다고 했을 때, 수를 하나씩 늘려가면 가장 큰 값은 마지막 날이기 때문이다.

 

print(max(map(max, graph))-1)

참고로 이 문장은 2차원 배열에서 가장 큰 값을 찾아낼 때 쓰는 코드이다. 각 array에서 가장 큰 값을 추출한 후, 거기서 max 값을 추출하는 방법이다.