백준 알고리즘 2573 - 빙산

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

2573번: 빙산

문제는 백준 알고리즘 사이트에서 확인하세요~

 

오늘 이야기할 문제는 그래프와 관련된 문제입니다.

 

빙하의 높이가 기록된 배열이 주어지고, 주어진 규칙에 따라 녹는 빙하에 대해서 묻는 문제네요~!

 

흥미로운 주제에요~

 

문제가 원하는 구체적인 정답은 다음과 같습니다.

 

"일년마다 인접해있는 0의 개수만큼 빙하가 (따로따로)녹을 때

빙하가 갈라져 두 덩어리가 되기 까지 걸리는 시간(년)은?"

 

이때 인접해있다는 것은 동서남북의 위치만을 나타냅니다.

 

각각의 배열 원소를 정점으로 생각하면, 인접해있음을 알기 위해선 

 

그래프 순회 알고리즘인 BFS와 DFS를 이용할 수 있겠습니다~!

BFS	QUEUE 이용. 이미 지난 곳을 다시 방문하지 않는다.
DFS	STACK 이용. 이미 지난 곳을 다시 방문하지 않는다.

저는 BFS를 이용해서 이 문제를 해결했는데요.

 

빙하의 높이가 기록된 배열을 편의상 '지도'라고 할게요.

 

머리속으로 문제를 어떻게 풀지 그려보면, 해가 지나면서 1) 올해 발생할 사건과 2) 과거에 발생한 사건

 

두 사건이 연관되어 진행됨을 알 수 있네요!

 

이 점을 이용하기위해 DP를 사용했어요~

 

먼저 한 해가 지날때 지도에 적힌 각각의 빙하가 얼마만큼 녹을지 알아내야합니다.

 

저는 빙하를 기준으로 인접한 0을 찾아서 해당 빙하가 얼마만큼 녹을지 배열 D에 따로 기록했습니다.

 

그리고 빙하가 위치한 정점 중 임의의 좌표를 BFS QUEUE에 삽입후

 

BFS를 수행하고 이전 년도와 올해 연도간의 상관관계를 찾기위해 배열 P에서 빙하의 위치에 연도를 기록했어요.

 

그리고 다시 연도가 바뀌면 빙하가 녹을 양을 파악하기 위해 지도를 찾아야합니다. 

 

이때 배열 P에 전년도 빙하 정보를 기록해둔것을 비교하면서 두덩어리가 된 빙하가 있는지 확인할 수 있습니다!

 

1. 빙하(정점)가 녹아 없어졌다(0)면?

      - > 지도에서 if문에 의해 더 이상 발견되지 않아야합니다.

 

2. 해가 지나고 지도에서 if문에 의해 발견된 빙하의 P 정보가 전년도가 아니라면?

      -> 빙하가 여러 덩어리로 쪼개졌음을 알 수 있습니다.

 

3. P 정보가 전년도가 아니면 알고리즘의 종료조건을 만족합니다.