[백준][BFS] 빙산

문제

2차원 배열로 빙산이 주어졌을 때, 1년이 지날 때마다 0인 바닷물과 인접한 만큼 빙산의 높이가 줄어든다. 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2573)

풀이

정답율이 낮은 문제여서 어려울 줄 알았는데 빙산을 녹이는 부분, BFS(또는 DFS)를 통해서 빙산의 덩어리가 두덩어리로 나누어질 때를 확인해주면 되는 문제입니다. 처음엔 이중 for문을 통해서 각 칸에서 빙산이라면 얼마나 녹아야하는지를 탐색하려했는데 빙산이 아닌 부분(0인 곳)이 많을 경우에는 시간이 많이 걸릴 것 같아서 처음 입력을 받을 때 queue를 통해서 따로 빙산을 저장해줬습니다. 그 다음엔 이 queue를 이용해서 처음 size만큼 pop을 시키면서 해당 빙산이 얼마나 줄어드는지를 확인했습니다. 이 때 바로 map의 빙산높이를 줄여버리면 다음칸에 영향이 가기때문에 높이가 줄어드는 칸은 따로 저장을 통해서 모든 빙산을 탐색한 다음 높이를 줄이도록 해주었습니다. 

1. 0이 아닌 칸이 들어있는 queue<int> bingsan;에서 각 칸의 높이가 얼마나 줄어드는지를 계산하고 녹아 없어지지 않는다면 bingsan에 push합니다.

2. 1번의 모든 탐색이 끝나면 해당 결과들을 map에 업데이트합니다.

3. bingsan의 front값에서 BFS 탐색을 시작하고, 탐색한 node의 개수와 큐 bingsan.size()가 같다면 하나의 덩어리인 것이고 만약 같지 않다면 덩어리가 분리된 것이므로 종료합니다. 같다면 다시 1번으로 돌아가서 반복합니다.

반복 횟수가 최소의 시간이므로 답이 됩니다. 그리고 체크해줘야 하는 조건이 하나 더 있는데 만약 다 녹을 때까지 두덩이로 분리되지 않는다면, 즉 3번에서 bingsan.size() == 0 이라면 답은 0이 되도록 if문을 추가해줘야합니다.

코드

https://github.com/kswim/Algorithm/blob/master/BFS/2573.cpp