[백준] 2573번 빙산 (Python)

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

2573번: 빙산

자존감을 올려주는 단순구현문제..ㅎㅎ

문제에서 시키는대로 구현했다 

 

1. 0이아닌 칸 찾기 

2. 찾은 칸의 상하좌우에 0 개수 세기 

3. 빙하가 녹을 좌표들을 모았다가 한번에 처리하기 

4. 1 ~ 3 반복하면서 현재 빙산 덩어리가 몇개인지 세어주기 --> count_iceberg() 함수에서 bfs로 빙산 덩어리를 카운트 함 

5. 4번 과정에서 빙하가 모두 녹아버리는 경우를 확인하기 위해 check_melted() 함수로 확인함 

from collections import deque

n, m = map(int, input().split())
board = []

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

def count_iceberg():
    cnt = 0
    visited = [[False] * m for _ in range(n)]

    def iceberg(sx, sy):
        queue = deque([])
        queue.append((sx, sy))
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and board[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))


    for i in range(n):
        for j in range(m):
            if board[i][j] and not visited[i][j]:
                visited[i][j] = True
                iceberg(i, j)
                cnt += 1


    return cnt


for i in range(n):
    data = list(map(int, input().split()))
    board.append(data)


def bfs():

    queue = deque([])
    pos = []

    for i in range(n):
        for j in range(m):
            if board[i][j]: # not 0
                queue.append((i, j, 0))
    while queue:
        x, y, time = queue.popleft()

        water = 0 # 바닷물 닿는 부분 개수
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not board[nx][ny]:
                water += 1
        if water > 0:
            pos.append((x, y, water))
    # queue 한번 다 돌고 처리해주기
    for x, y, water in pos:
        board[x][y] -= water
        if board[x][y] < 0:
            board[x][y] = 0
answer = 0

def check_melted():
    result = 0
    for i in range(n):
        result += sum(board[i])
    if result == 0:
        return True
    return False

while True:
    if count_iceberg() >= 2:
        break
    if check_melted():
        answer = 0
        break
    bfs()
    answer += 1 # 1 year passed
print(answer)