[코드트리 조별과제 / Python] 빙하 (BFS)

문제

주어진 문제는 N×M 크기의 격자에서 빙하(1)와 물(0)의 상태를 표현하는 배열을 통해, 빙하가 전부 녹는 데 걸리는 시간과 마지막으로 녹은 빙하의 크기를 계산하는 것이다. 빙하는 매 초마다 상하좌우로 인접한 물과 접촉하여 동시에 녹는데, 빙하로 둘러싸여 있는 물의 경우에는 붙어 있는 빙하를 녹이지 못한다. 최종적으로 빙하가 모두 녹을 때까지의 시간과 마지막으로 녹은 빙하의 크기를 출력해야 한다.

 

풀이

• 바깥쪽에 있는 물이 빙하와 접촉하면 해당 빙하가 녹지만, 안쪽에 있는 물은 빙하에 영향을 미치지 않는다는 점이 중요하다.
• 이를 해결하기 위해 BFS 알고리즘을 사용하여 바깥쪽 물을 중심으로 탐색하면서 빙하를 만나면 녹이도록 한다.
• 이 과정에서 빙하가 녹은 자리는 물의 영역으로 간주될 수 있기 때문에, 기존 배열에서 즉시 녹이지 않고 새로운 배열에서 빙하를 녹이는 방식으로 처리한다. (빙하의 위치를 리스트에 담아 기존 배열에서 한 번에 녹이는 방법도 가능하다.)
• 또한, 초기 빙하 개수를 미리 계산해 두면 마지막으로 빙하가 녹는 시간을 판단하는 데 도움이 된다.

 

Python 코드

from collections import deque

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
total = sum(sum(row) for row in arr)  # 전체 빙하의 개수 카운트

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def melt():
    new = [[arr[i][j] for j in range(m)] for i in range(n)] # 녹은 빙하가 표시될 배열
    visited = [[0] * m for _ in range(n)]

    q = deque()
    q.append((0, 0))  # 외부에서 시작 / 조건에 따라 (0,0)은 무조건 바깥에 위치한 물
    cnt = 0  # 녹은 빙하 개수
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if not in_range(nx, ny):
                continue
            if visited[nx][ny]:
                continue
            visited[nx][ny] = 1
            
            if arr[nx][ny] == 1:  # 빙하인 경우
                new[nx][ny] = 0  # 녹임
                cnt += 1
            else:
                q.append((nx, ny))  # 물인 경우 큐에 추가
    return cnt, new

t = 0
while total:
    cnt, arr = melt() # 녹은 빙하가 체크된 배열로 업데이트
    t += 1
    total -= cnt
    if total == 0:
        print(t, cnt)
        break

 

 

 

문제출처 : https://www.codetree.ai/missions/2/problems/glacier/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석