G5 7576. 토마토

문제 보기 :  7576번: 토마토

---

문제

• 정답률 : 37%

---

작성 코드

from collections import deque

def bfs(graph):
    directions = [(-1,0),(0,-1),(0,1),(1,0)]
    while dd:
        x,y = dd.popleft()
        for dx,dy in directions:
            xx = x+dx ; yy = y+dy
            if 0<=xx<n and 0<=yy<m and graph[xx][yy]==0:
                graph[xx][yy] = graph[x][y]+1
                dd.append((xx,yy))

m,n = map(int,input().split())
ls = [list(map(int,input().split())) for i in range(n)]
dd = deque()
for i in range(n):
    for j in range(m):
        if ls[i][j]==1:
            dd.append((i,j))

bfs(ls)

count = 0
for i in range(n):
    for j in range(m):
        if ls[i][j] == 0: 
            print(-1)
            ## 즉각 종료
            exit(0)
        count = max(count, ls[i][j])

if count >= 1:
    print(count-1)
else:
    print(0)

---

풀이

bfs 알고리즘을 사용했고, bfs 함수 내 graph는 '입력'으로 받는 ls와 같으며, 정석적인 bfs 알고리즘 문제의 visited 리스트를 담당하기도 한다.

가로 m, 세로 n에 해당하는 리스트를 ls로 두고, 이 리스트 내 좌표 중 값이 1인 좌표를 dd라는 deque에 더한다.
이후 dd에서 하나의 리스트씩 빼면서(popleft) x,y 좌표를 확인하는데
먼저 x,y의 좌표 값은 무조건 1이기 때문에 확인할 필요가 없다.
그리고 xx, yy의 좌표를 확인해야하는데 이 값이 0이라면, graph[x][y]+1로 업데이트한다.

dd에 아무 원소가 없으면 bfs 함수를 종료하는데, ls에 0이 있다면 -1을 출력하며 프로그램을 종료하고
아니라면 max값으로 count를 업데이트한다.count가 1 이상이면 count-1을 출력하며 마무리하고, 0이면 0을 출력하고 종료한다.