[알고리즘] 백준 7576번
문제
https://www.acmicpc.net/problem/7576
풀이
오늘도 역시 BFS 문제를 풀어보았습니다. 사실 BFS 문제가 DP보다 잘 풀려서 BFS에 더욱 손이 가더라구요. DP를 연습해야하는데 말이죠...하여튼! 오늘 풀어본 BFS 문제 역시 제가 지금까지 풀어온 BFS 문제와 크게 다를 것이 없습니다. 하지만 제가 생각하지 못한 반례가 존재하였기 때문에 약간은 시간을 소비했는데 정답률에 비해 그렇게 어렵지 않은 문제였습니다.
다음은 저의 풀이 과정입니다.
- BFS를 통해 전체를 탐색하는데 레벨이 곧 구해야하는 최소 날짜이기 때문에 이 부분은 이전에 풀어보았던 2178번과 같은 방법을 사용해주었습니다.
- 처음에는 단순히 위에 것만 생각하고 반례를 생각하지 않았습니다. 하지만 모두 익지 않은 경우의 반례를 생각해야만 했습니다.
- 반례는 다음과 같습니다.
1 -1 0
-1 0 0
0 0 0
위와 같은 반례일 경우 보관 박스의 토마토들은 전부 익지 못합니다. - 탐색이 끝난 후 0인 요소가 존재하면 모두 익지 않은 경우이고, 배열의 모든 값의 합이 N*M이면 배열의 모든 값이 1이라는 뜻이고 이는 애초에 모든 토마토가 익었다는 의미입니다. 그리고 이 둘의 경우를 제외하고 배열에서 가장 큰 값을 찾으면 그 값이 토마토가 모두 익는데 걸리는 최소 일수라는 것을 알 수 있습니다.
다음은 저의 코드입니다. 사실 더 깔끔하게 좋은 코드들도 많지만 제가 직접 푼 코드를 올리고 싶어서 수정하지 않도록 하겠습니다.