문제 링크

빙산

문제 설명

N*M크기의 지도에 빙산을 표현하려고 한다. 0은 바다, 0이 아닌 수는 빙산의 높이를 나타낸다.

빈칸을 0 이라고 생각했을때, 빙산을 위와 같이 표현할 수 있다.

빙산의 높이는 해당 칸의 동서남북 네방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 따라서 위 그림의 빙산은 일년후와 이년후는 각각 다음과 같이 변형된다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

문제 풀이

무한 루프를 돌면서 빙산이 2개로 분리되지 않았으면, 빙산을 돌면서 동서남북 중 바다인 부분을 세서 빙산의 높이를 갱신한다. 빙산의 높이보다 둘러싼 0칸의 갯수가 많거나 같아서 전부 녹은 (0이 된) 칸은 따로 표시를 해줘야 함을 주의해야 한다.
빙산이 2개로 분리되었는지 검사하는 부분은 bfs를 이용하였다. bfs를 이용해서 빙산 1개를 이루는 칸의 갯수를 세고, 이 값이 iceberg 배열(빙산을 이루는 모든 칸의 좌표 저장)의 길이와 일치하는지 검사한다.

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
board = []
iceberg = []
years = 0

for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] != 0:
            iceberg.append([i,j])
    board.append(tmp)

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

def bfs():
    count = 0
    queue = deque([iceberg[0]])
    visited = [[0]*M for _ in range(N)]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and board[nx][ny] != 0 and visited[nx][ny] == 0:
                count += 1
                visited[nx][ny] = 1
                queue.append([nx, ny])
    
    if count == len(iceberg):
        return True
    else:
        return False

while True:
    #2개로 분리됐는지 ?
    if len(iceberg) == 0:
        break
    if bfs():
        years += 1
        melted = [[0]*M for _ in range(N)]
        j = 0
        while j < len(iceberg):
            x, y = iceberg[j]
            #네방향 중 바다인 부분 체크
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and board[nx][ny] == 0 and melted[nx][ny] != 1:
                    board[x][y] -= 1
                    if board[x][y] == 0:
                        melted[x][y] = 1
                        iceberg.remove([x,y])
                        j -= 1
                        break
            j += 1
    else:
        break
if len(iceberg) == 0:
    print(0)
else:
    print(years)

쉽지 않았다고 한다 ,,~