문제 링크

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

문제 설명

• board에 좌표의 빙산의 높이가 주어진다
• 일 년에 각 좌표마다 바다(0)와 인접한 수만큼 줄어든다.
• 처음 한 덩어리였던 빙산이 두 덩어리가 되는 것은 몇 년 후인지 출력

풀이

• 각 좌표를 돌면서
• not visited일 경우 덩어리 수 += 1
• 덩어리 수가 1 이하일 때 BFS
• BFS를 하면서 각 좌표 별 인접한 바다 수를 계산
• 좌표마다 바다 수만큼 높이를 줄인다
• 만약 좌표를 돌면서 not visited인 좌표가 더 있다면 덩어리가 나누어진 것이므로 종료
• 반복
• 만약 덩어리 수가 0인 채로 종료했다면 0 출력

코드

def init():
    import sys
    ipt = sys.stdin.readline
    n, m = map(int, ipt().split())
    board = [list(map(int, ipt().split())) for _ in range(n)]
    dy = [1,-1,0,0]
    dx = [0,0,1,-1]
    return n, m, board, 0, 0, dy, dx


def bfs(start):
    from collections import deque
    q = deque([start])
    sy, sx = start
    visited[sy][sx] = True
    while q:
        cy, cx = q.popleft()
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if not visited[ny][nx] and board[ny][nx] > 0:
                visited[ny][nx] = True
                q.append((ny, nx))
            if board[ny][nx] <= 0:
                sea[cy][cx] += 1


def decrease():
    for y in range(n):
        for x in range(m):
            board[y][x] -= sea[y][x]


n, m, board, num, year, dy, dx = init()
while True:
    visited = [[False] * m for _ in range(n)]
    sea = [[0] * m for _ in range(n)]
    num = 0
    for y in range(1, n-1):
        for x in range(1, m-1):
            if board[y][x] > 0 and not visited[y][x]:
                num += 1
                if num >= 2:
                    break
                bfs((y, x))
                decrease()
        if num >= 2:
            break
    if num != 1:
        break
    year += 1
if num:
    print(year)
else:
    print(0)