2573. 빙산 (Python)

2573번: 빙산

 

풀이

 빙산의 정보를 icebergs 배열에 (행, 열, 높이)의 형태로 저장해둔다. 그리고 다음 과정을 수행한다.

1. 빙산을 녹이면서 높이가 0이 되는 빙산과 그렇지 않은 빙산을 나누어 저장한다. 그 후 맵에 빙산들의 높이를 업데이트한다. 
2. 새로운 빙산 정보에 대하여 bfs를 진행한다.
   1. 임의의 빙산을 시작점으로 잡고 bfs를 수행한다.
   2. bfs를 수행하면서 만난 빙산의 개수를 카운트한다. 
   3. 카운트 된 빙산의 개수와 icebergs 배열에 있는 빙산의 개수가 같다면 빙산이 한 덩어리임을 의미한다. 
   4. 그럴 경우 위의 과정을 반복한다. 

 

코드

import sys
input = sys.stdin.readline


# 빙산이 녹는 과정을 처리하는 함수 
def meltIceberg():
    newIcebergs = [] # 녹고 난 후의 빙산 정보 -> (행, 열, 새로운 높이)
    zeroIceberg = [] # 녹고 난 후 높이가 0이 된 빙산 위치 정보 -> (행, 열)

    # 현재 빙산에 대해서 녹는 과정 처리
    for (x, y, height) in icebergs:
        count = 0 # 바닷물에 접해 있는 부분의 개수 
        for (dx, dy) in dir:
            nx = x + dx
            ny = y + dy

            if board[nx][ny] == 0:
                count += 1 # 바닷물에 접해 있는 부분 1 증가 

        # 현재 높이에서 바닷물에 접해 있는 부분만큼 빼주고 만약 음수가 될 경우 0으로 설정
        height = max(0, height - count)

        # 다음 높이가 0일 경우 zeroIceberg 배열에 추가
        if height == 0:
            zeroIceberg.append((x, y))
        else: # 그렇지 않을 경우 newIcebergs 배열에 추가 
            newIcebergs.append((x, y, height))
    
    # board에 새로운 빙산의 높이 업데이트 
    for (x, y, height) in newIcebergs:
        board[x][y] = height
    for (x, y) in zeroIceberg:
        board[x][y] = 0

    # 높이가 0이 아닌 빙산들만 return
    return newIcebergs


# 몇 개의 그룹이 있는지 체크하기 위한 함수 
# 임의의 빙산 위치에서 bfs를 수행했을 때 탐색이 진행된 빙산의 개수가 icebergs 배열에 있는 빙산의 개수와 같다면 한 덩어리임을 의미한다.
# 다를 경우 또 다른 덩어리가 있다는 의미 
def checkGroup():
    visited = [[False for _ in range(M)] for _ in range(N)]
    q = [(icebergs[0][0], icebergs[0][1])] # icebergs 배열의 첫 번째에 있는 빙산 좌표를 큐에 넣는다.
    visited[icebergs[0][0]][icebergs[0][1]] = True

    count = 1 # 탐색된 빙산의 개수 
    while q:
        x, y = q.pop(0)

        for (dx, dy) in dir:
            nx = x + dx
            ny = y + dy

            if visited[nx][ny] or board[nx][ny] == 0:
                continue

            q.append((nx, ny))
            count += 1 # 탐색 빙산 개수 1 증가
            visited[nx][ny] = True

    # 빙산이 한 덩어리인 상태이면 True를 return
    if count == len(icebergs):
        return True
    else: # 빙산이 여러 덩어리인 상태라면 False를 return 
        return False


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [[] for _ in range(N)]
    icebergs = [] # 빙산의 정보 -> (행, 열, 높이)
    dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    for i in range(N):
        boardInput = list(map(int, input().split()))

        for j in range(M):
            board[i].append((boardInput[j]))

            if boardInput[j] != 0:
                icebergs.append((i, j, boardInput[j]))

    res = 0

    while True:
        res += 1 # 시간 증가
        icebergs = meltIceberg() # 빙산이 녹고 새로운 빙산 정보를 icebergs에 대입

        # 모든 빙산의 높이가 0이 되어 icebergs에 빙산의 정보가 없을 경우 
        # res를 다시 0으로 초기화하고 종료
        if len(icebergs) == 0:  
            res = 0
            break
        
        # checkGroup의 값으로 False가 반환 되었다면
        # 이는 빙산이 두 덩어리 이상으로 이루어져 있음을 의미하므로 과정 종료 
        if not checkGroup():
            break

    print(res)