[백준] 2573. 빙산
빙산 문제는 그래프 탐색 알고리즘인 BFS와 DFS를 둘 다 사용하여 풀 수 있다.
문제는 크게 두 가지 흐름으로 나타낼 수 있다.
- 시간이 흐를 수록 빙산이 녹는 과정
- 빙산이 녹은 후 나눠진 빙산을 세는 과정
두 가지 흐름 중, 1번 빙산이 녹는 과정은 BFS를 통해 가장자리의 빙산의 높이를 줄여나갈 수 있다. 가장자리의 빙산은 어떻게 판단할 수 있을까. 바로 주변에 바다가 있는 경우다. 따라서 한 위치에서 상, 하, 좌, 우의 위치의 값이 0이면 가장자리의 빙산이라 할 수 있다. 시간을 녹을 때마다 높이를 줄여나가면 된다. 맨 처음 상태에서 가장자리의 위치한 빙산의 좌표를 큐에 저장한다. 이후 시간이 흐를 때마다 큐에 저장한 빙산의 좌표를 하나씩 꺼내서 높이를 줄여나간다. 단, 한 가지의 주의할 점은 빙산의 상, 하, 좌, 3개의 부분이 0이라면 빙산의 높이는 3씩 줄어나가는 점이다. 빙산의 인접한 상,하 좌, 우에 대한 상태를 따로 표시하지 말고 빙산를 큐에 여러 차례 넣자.
2번 과정은 DFS를 통해 빙산의 개수를 판단한다. BFS로 시간이 흐를 때 마다 중간에 DFS를 통해 빙산의 개수를 파악하고 1개 아니라면 중지하자. 중요한 부분은 빙산의 개수를 시간이 흐르기 전에도 확인하는 것이다.