백준 7576번 토마토

문제 설명

이번 문제는 토마토를 보관할 경우, 하루가 지나면 익은 토마토 주변의 토마토가 익게 될 경우 모든 토마토가 익으려면 며칠이 걸리는지 구하는 문제입니다.

• 주변은 상하좌우를 말합니다.
• 보관 창고에는 빈 공간이 존재합니다.
• 모든 토마토가 익을 수 없는 경우 -1

 

문제 풀이

아이디어

BFS

각 익은 토마토로부터 주변의 토마토가 익게 되므로 BFS를 통해 익은 토마토의 주변부터 탐색할 수 있도록 합니다.

 

풀이

BFS

현재 익은 토마토의 좌표를 queue에 넣어줍니다.

이 때, 첫 날 익은 토마토를 모두 한 배열안에 넣어준다음 이것을 queue에 넣어줍니다.

queue= [ [ [r1,c1], [r2,c2], ... ] ]

이런 식으로 진행할 경우 진행된 날짜를 세기 편한 것 같습니다.

 

queue의 원소를 pop하여 내부에 있는 좌표 배열을 반복문을 통해 주변의 안 익은 토마토를 탐색할 수 있도록 합니다.

for r,c in queue.pop():
    for i in range(4):
        nr,nc=r+dx[i],c+dy[i]

현재 토마토의 주변 좌표 중 빈 칸이 아니고 익은 토마토가 아닐 경우 새로운 배열에 넣어줍니다.

if not (0<=nr<N and 0<=nc<M) or tomato[nr][nc]!=0:
    continue
            
tomato[nr][nc]=1
count+=1
newTemp.append([nr,nc])

새로운 배열(newTemp)를 다시 queue에 넣어주고 while문을 반복하여 BFS를 진행합니다.

또한, 날짜를 카운트 해줍니다.

queue.append(newTemp)
day+=1

 

 

해결

이번 문제는 오랜만에 다시 시도한 알고리즘 문제입니다. 그래프 문제로, 오랜만에 도전하는 만큼 조금 쉬운 문제로 도전해봤습니다. 점차 어려운 문제를 도전하여 solved.ac 랭크를 다시 올려보도록 하겠습니다!

 

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/7576.py