[백준] 2573. 빙산 - python

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

난이도: 골드4

알고리즘: BFS

풀이과정

빙산이 두 부분 혹은 그 이상으로 나누어지는 시점을 확인하는 문제다. BFS를 이용하면 이를 쉽게 확인할 수 있다.

 

먼저 입력의 크기를 살펴보면, 행 열을 나타내는 n과 m의 크기가 3 ~ 300 으로 시간 복잡도는 고려하지 않아도 된다.

 

반복문을 돌며 빙산이 나누어져 있는지 검사해야 한다. BFS를 활용하여, 0이 아닌 칸에서부터 상하좌우로 방문처리를 해준다. BFS를 적용한 후에 0이 아닌 칸이면서 방문처리가 되지 않은 칸이 있다면 나누어진 빙산이 있다는 뜻이므로, 걸린 시간을 출력하고 종료하면 된다.

 

빙산이 나누어지지 않고 전부 녹을 경우에는 0을 출력해야 하므로, 반복문을 돌며 모든 칸이 0이 되는 경우에는 반복을 종료하고 0을 출력한다.

소스코드

from collections import deque
from copy import deepcopy


def is_zero():
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] != 0:
                return False
    return True


def bfs():
    global visited
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                visited[i][j] = 1
                dq = deque()
                dq.append((i, j))
                while dq:
                    cur_y, cur_x = dq.popleft()
                    for i in range(4):
                        new_y = cur_y + dy[i]
                        new_x = cur_x + dx[i]
                        if 0 <= new_y < n and 0 <= new_x < m and board[new_y][new_x] != 0:
                            if not visited[new_y][new_x]:
                                visited[new_y][new_x] = 1
                                dq.append((new_y, new_x))
                return


n, m = map(int, input().split())
board = []
answer = 0
for _ in range(n):
    board.append(list(map(int, input().split())))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while not is_zero():
    visited = [[0 for _ in range(m)] for _ in range(n)]
    # bfs 1번 수행
    bfs()

    # 빙산이 나누어졌다면 종료
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0 and not visited[i][j]:
                print(answer)
                exit()
    new_board = deepcopy(board)
    # 빙산 녹이기
    for i in range(n):
        for j in range(m):
            if board[i][j] != 0:
                for k in range(4):
                    ny = i + dy[k]
                    nx = j + dx[k]
                    if 0 <= ny < n and 0 <= nx < m and board[ny][nx] == 0:
                        if new_board[i][j] > 1:
                            new_board[i][j] -= 1
                        else:
                            new_board[i][j] = 0
    board = new_board
    answer += 1
print(0)

 

시행착오

 

빙산 녹이기를 수행할 때, 직접 board에 값을 갱신하면 다음 갱신에 영향을 줄 수 있으므로 new_board를 할당해 주어야 한다.