[BOJ] 2573: 빙산

문제 바로가기

풀이

문제를 두 단계로 나눌 수 있다.

1. 모든 빙산에 대해 바다와 맞닿아있는 면적 갯수 계산
2. 빙산 업데이트 후 2개 이상으로 분리되었는지 확인

를 빙산이 없어지거나 빙산이 분리될 때 까지 반복해주면 된다.

주의할 점은 모든 빙산에 대해 계산 후 한번에 업데이트를 해줘야 한다.

1. 모든 빙산에 대해 바다와 맞닿아있는 면적 갯수 계산

상하좌우에 0의 갯수만큼 나중에 빙산을 업데이트 해주면 된다.
그래프 내의 빙산을 담고 있는 node 배열에 대해 똑같은 크기를 갖는 diff 배열에 값을 저장해서 계산했다.

2. 빙산 업데이트 후 2개 이상으로 분리되었는지 확인

node를 순회하며 diff값을 이용해 update 해주면 된다.

이후 빙산들에 대해 1) 빙산이 여러개로 분리 2) 아예 사라지는 경우

에 대해 체크해줘야 한다.

1)의 경우 빙산 하나에서 BFS를 했을 때 모든 node에 대해 방문이 되어야 한다. 그렇지 않으면 현재까지 진행한 값(year)를 출력하고 종료한다.
2)는 빙산이 분리되지 않고 다 녹는 경우이다. 0을 출력하고 종료한다.

1)과 2) 둘다 만족하지 않으면 year를 증가시키고 1을 다시 시작하면 된다.