백준 2573. 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

처음에 단순히 시도한 방법은

 

1. 각 빙산마다 인접한 네방향을 탐색해 녹여야 하는 크기를 저장해놓고

2. 빙산들을 계산한만큼 녹이고 

3. dfs 탐색으로 덩어리의 갯수를 계산한다.

 

1번과 2번을 따로한 이유는 계산하면서 바로 해당 빙산을 녹여버리면 인접한 빙산이 영향을 받기 때문이다.

예를들어 [2][2]지점의 빙산이 계산결과 녹아 없어져 0이 되버리면 [2][3] 지점 빙산은 [2][2] 빙산에 인접해있기 때문에 녹여야 하는 크기가 1증가해버린다.

 

그런데 이렇게 하면 1년 탐색하는데 NxM 반복문이 3번이나 필요하다. 

어쨌든 우선 이렇게 제출해봤는데 역시 시간초과를 받았다.

 

---

시간복잡도를 줄이기 위해 반복문을 어떻게든 줄일수 없을까 고민해봤다.

우선 1번. 각 빙산마다 인접한 네방향을 탐색해 녹여야 하는 크기를 저장 은 아무리 생각해도 수행할수 밖에 없었다.

따라서 2번과 3번 반복문을 따로하지 않고 통합할수 없을까 생각해봤고 이 방법으로 통과했다.

NxM 반복문을 돌면서 빙산들을 탐색하는데 만약 (빙산의 크기 - 녹여야 하는 크기)가 0 이하가 된다면 해당 빙산은 녹여 없에버린다 (0으로 만든다).

0이하가 아니라면 이번 년도에는 녹아 없어지지 않을 빙산이므로 해당 지점부터 dfs 탐색을 시작한다.

dfs 탐색을 하면서 인접 빙산으로 옮겨가는데, 여기서도 마찬가지로 인접 빙산이 녹아 없어질 예정이라면 0으로 만들어버리고 이동하지 않고, 아직 없어지지 않는다면 녹아야 하는 크기만큼 녹이고 이동을 반복한다.

물론 dfs 탐색을 하는동안 방문지점은 체크하고 다시 방문하지 않도록 해야한다.

dfs 탐색을 수행한 횟수가 빙산 덩어리의 갯수가 된다.

 

이렇게 하면 첫번째 방법과 달리 2번의 NxM 반복문으로 빙산들을 녹이고, 덩어리의 크기도 계산할수 있다.

 

---

추가한다.

일반적으로 bfs 탐색이 dfs 보다 훨씬 빠르므로 위에서 빙산 덩어리의 탐색을 dfs가 아닌 bfs로 하면 반복분 3개로도 해결할수 있을것 같다.