🥇[백준] 7576 토마토 (골드5) / BFS

문제요약

나의 코드 및 설명

from collections import deque

def bfs():
    global days
    while queue: #큐가 빌때까지 반복 수행
        x,y = queue.popleft()
        #동서남북 네 방향으로 토마토가 익을 수 있는지 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #전체 박스를 벗어난다면, 지나간다.
            if nx<0 or ny<0 or nx>=m or ny>=n:
                continue
            #다음 좌표가 아직 안익은 토마토이고, 방문하지 않았다면
            if board[ny][nx] == 0 and visited[ny][nx] == 0:
                #다음 좌표의 토마토를 익었다고 처리하고
                board[ny][nx] = 1
                #방문 테이블 값을 1 증가시킨다.
                visited[ny][nx] = visited[y][x] + 1
                #날짜 변수에 다음 방문 테이블 값 저장
                days = visited[ny][nx]
                queue.append((nx,ny))

m, n = map(int, input().split()) #m:가로 칸의 수 / n:세로 칸의 수
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

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

visited = [[0]*m for _ in range(n)]
days = 0
ans = 0
queue = deque()

#먼저, 익은 토마토(1) 좌표를 queue에 추가한다.
#queue에 넣어주는 작업을 먼저 해야 모든 익은 토마토의 좌표부터 탐색을 시작한다.
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            queue.append((j,i))

bfs() #모든 익은 토마토의 좌표를 큐에 저장한 후, bfs 수행
ans = days #정답은 날짜 변수에 저장된 값

#board 좌표 값을 하나씩 확인하며, 아직도 0이 있다면, 토마토는 익을 수 없는 것이므로,
#정답은 -1 
for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            ans = -1
            break
    if ans == -1:
        break

print(ans)

피드백

처음엔 익은 토마토의 좌표가 여러개일수도 있다는 생각을 전혀 못하고 문제를 풀었다가 예제 입력값을 다시 보고나서 당황했다. 그동안 전체 그리드를 순차적으로 방문하여 bfs를 수행할 조건에 해당하면 bfs를 수행하면서 좌표를 그때그때 넣어주었는데 , 이번 문제의 경우엔 먼저 전체 그리드를 방문하면서 큐에 좌표를 넣어야한다. 그래야 모든 익은 토마토의 좌표를 큐에서 pop하면서 동시에 탐색을 진행하기 때문이다. 바보같이 이것을 전혀 생각하지 못했다. 단순히 코드에 익숙해지지 말고, 더 생각하면서 풀도록 해야겠다. 문제를 풀어 뿌듯하면서도, 이전에 반복한 코드에만 익숙해진게 아닐까 싶어서 반성하게 된 문제.. 더 노력하자