백준 온라인 저지 2573번 빙산 문제 자바 풀이 입니다.
이는 bfs를 이용하는 문제입니다.
문제 링크는 아래에 있습니다!!
https://www.acmicpc.net/problem/2573
이 문제는 골드4로 랭크된 문제에요. 하지만 bfs의 개념만 알고 구현할 줄 안다면 그리 어렵지 않습니다.
저는 bfs를 stack을 이용하여 구현하였습니다.
이와 비슷한 문제로 보물섬 문제가 있는데요 백준 2589번도 같이 풀어 보시면 좋을 것 같아요
https://www.acmicpc.net/problem/2589
문제정리
1. 빙산은 양의 정수, 그 외 바다는 0이다.
2. 빙산에 붙어있는 0의 개수만큼 빙산의 높이가 감소된다. ( 단 빙산의 높이는 0보다 더 줄어들지는 않는다.)
3. 그러다가 빙산이 덩어리로 떨어질 때 두 덩어리로 분리되는 최초의 시간을 구한다.
* 만약 빙산이 다 녹아 없어질때까지 두 덩어리로 분리되지 않는다면 0을 출력한다.
문제풀이
1. bfs로 0이 아닌 수를 찾아서 상하좌우를 탐색하여 인접한 0의 개수에 따라 높이 값을 바꿔줍니다.
* 이때 그때 그때 값을 갱신해주게 되면 녹아서 0으로 된것을 원래 바다로 인식해서 높이가 연쇄적으로
높이가 더 낮아지기 때문에 모든 값을 한 번에 바꿔준다. 저는 리스트에 넣어 놓고 탐색을 마친 후 한 번에 값을 update해주었습니다.
2. 영역의 수는 dfs로 찾으러 들어가는 수로 check한다.
3. 다 녹아서 영역이 0이 된다면 0을 출력하고 끝낸다. 영역이 2가 되는 경우도 출력하고 끝난다.
bfs로 탐색하는 부분은 0이 아닌 수들을 계속 따라가면서 그 주변에 붙어있는 0의 개수를 따져 주면 된다.
그러면 간단하게 풀 수 있습니다.
백준 2573번 빙산 자바 코드