6112 : 빙산 녹이기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 격자에 빙산의 높이가 자연수로 주어지고 바다는 0으로 표시됩니다.
매년 빙산은 동서남북 네 방향으로 붙어있는 바다(0)의 개수만큼 높이가 감소하며, 0 미만으로는 떨어지지 않습니다. 매년 녹아 없어지는 빙산 높이를 갱신한 뒤, 빙산(높이 > 0)들이 두 개 이상의 컴포넌트로 분리되는 데 필요한 최초의 시간을 구하시오. 다 녹을 때까지 분리되지 않는다면 0을 출력합니다.
매년 빙산은 동서남북 네 방향으로 붙어있는 바다(0)의 개수만큼 높이가 감소하며, 0 미만으로는 떨어지지 않습니다. 매년 녹아 없어지는 빙산 높이를 갱신한 뒤, 빙산(높이 > 0)들이 두 개 이상의 컴포넌트로 분리되는 데 필요한 최초의 시간을 구하시오. 다 녹을 때까지 분리되지 않는다면 0을 출력합니다.
입력 설명
첫째 줄에 격자의 세로 크기 N과 가로 크기 M (3 ≤ N, M ≤ 300)이 주어집니다.
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다. 가장자리 행과 열은 항상 0(바다)입니다.
둘째 줄부터 N개의 줄에 격자의 정보가 공백 구분되어 주어집니다. 가장자리 행과 열은 항상 0(바다)입니다.
출력 설명
빙산이 두 덩어리 이상으로 분리되는 최초의 년도를 출력합니다. 완전히 녹을 때까지 분리되지 않는다면 0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
매 단계(1년)마다 2차원 배열 전체를 순회하여 BFS 연결 요소를 탐색하고, 컴포넌트의 수가 2 이상인지 혹은 0인지를 판정하여 루프를 멈추거나 녹이는 처리를 계속하십시오.