[BOJ 7576] 토마토

Breadth-First Search

[BOJ 7576] 토마토

문제

구조화

• 앞 선 문제와 유사함.
• 탐색할 토마토 좌표 생성
• 익은 토마토는 1, 안익은 토마토는 0
• 익은 토마토가 안익은 토마토에게 영향을 주므로, 시작 지점은 이미 익어있는 토마토
• 이를 위해 토마토들의 좌표를 입력받은 후 값이 1인 토마토의 좌표를 큐에 추가
• 순회 시 인덱싱은 [y][x] 형태
• BFS로 탐색하되, 이동은 4방향으로 가능
• 초기 좌표가 1인 토마토를 기준으로 BFS 탐색
• 현재 좌표가 1이고, 이동 가능 공간의 좌표가 0일 경우 1씩 증가하여 tomato 값 수정
• start가 1이므로 -1하여 출력

예제 시각화

해답

from collections import deque
import sys
input = sys.stdin.readline
m,n = map(int, input().split())
tomato = []
a=deque()
for i in range(n):
    data = list(map(int, input().split())) 
    tomato.append(data)
for i in range(n): # y
    for j in range(m): # x
        if tomato[i][j]==1:
            a.append([i,j]) # 미리 다른 지점의 영향을 끼치는 익은 토마토의 위치를 큐에 저장
            
dx=(0,0,-1,1) # x 이동 가능 영역
dy=(1,-1,0,0) # y 이동 가능 영역
def bfs():
    while len(a): 
        y,x = a.popleft() # 익은 토마토인 1의 좌표를 기준으로 BFS 시작
        for i in range(4):
            new_x = x+dx[i] # 이동 가능한 x좌표
            new_y = y+dy[i] # 이동 가능한 y좌표
            if new_x>=m or new_y >=n or new_x<=-1 or new_y <= -1: # 이동가능영역이 아닌 경우 밑에 코드 무시
                continue
            else:
                if tomato[new_y][new_x]==0: # 이동 가능한 지점 중 아직 익지 않은 경우
                    tomato[new_y][new_x] = tomato[y][x]+1 # 익은 토마토를 기점으로 1씩 추가
                    a.append([new_y,new_x]) # 새로 익은 토마토의 좌표를 큐에 추가
bfs()
ans=0 # 정답 초기화
for i in tomato:
    if 0 in i: # 익지 않은 토마토가 존재한 경우 다 채울 수 없는 Case
        ans=0 # 하루를 빼주기 떄문에 -1을 출력하기 위해 0대입 후 반복문 탈출
        break
    else:
        ans = max(max(i),ans) # 다 채워진 토마토 판을 순회하며 max값 도출
print(ans-1) # 시작 토마토의 값이 1이므로, 하루를 빼줘야 함.