[BOJ][7576번] - 토마토

안녕하세요 Dibrary입니다.

이번에는 그래프 탐색 + 약간의 생각을 사용해야 풀 수 있는 문제 입니다.
(참고로 저는 생각을 하지 못해서 어려웠었죠;;)

 

이 문제를 보자마자 떠오른 생각은

1. 아 확산이 되네? BFS또는 DFS로 퍼뜨려 나갈 수 있겠다.
2. 근데 시작점이 한 개가 아니네....? 헐

생각 1번을 구현하기는 어렵지 않습니다. 문제는 '시작점'이 여러 개 인 것을 해 본 적이 없다는 것이었죠.

 

이 문제를 풀 때 생각해볼 2가지 아이디어가 있습니다.

먼저 잘 생각해 보면 시작점이 여러 개인 것은 그다지 중요하지 않습니다.
BFS를 사용한다고 할 때, 우리는 해당 '위치'에 대해서 뭘 고려할까요?
'방문 했느냐' / '방문 안했느냐' 입니다. 즉, 시작점이 여러 개라 한들 방문해버리면 어차피 거긴 안가게 되는 것이죠.

 

그리고, 우리는 '다 익었을 때' 며칠이 걸리느냐를 알아야 합니다. 즉, 

채우는 곳에 채워지는 날짜를 써 넣으면 각 위치별로 '언제' 방문처리가 이뤄지는지를 알 수 있게 되는 것이죠.
다시말하면 이 '언제'값 중에 가장 큰 값이 전부 다 찼을 때의 '소요 시간'이 됩니다.

 

---

코드는 아래와 같습니다.

bfs 함수에서 각 위치별로 '상, 하, 좌, 우' 4방향만을 고려하는데 조건문으로 '방문 여부'만을 고려하는 것을 알 수 있습니다.

방문을 하지 않았다면? 지금 위치에서 '한번 더' 나아가야 되는 것이므로 현재값 + 1을 써주므로써 방문하는 데 걸린 시간을 기록하게 되는 것이죠.

(위 코드는 제가 확인차 보고자 하는 print문이 몇 개 들어 있습니다.)

 

 

이상으로 '시작점이 여러 개인 BFS(혹은 DFS) 풀어보기'를 마치겠습니다.

처음에 직면했을 때가 당황스럽지, 이해를 하고 나면 다음엔 시간이 그리 오래 걸리지도 않는 것 같네요.