[파이썬] 백준 알고리즘 No.2573 빙산

나의 코드

import copy
import sys
from collections import deque
input = sys.stdin.readline
from copy import deepcopy


def go(x, y):
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
            count += 1
    tmp[x][y] = max(0, tmp[x][y] - count)


def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        a, b = queue.popleft()
        visited[a][b] = True

        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))


result = 0
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 시작할 때 부터 전부 녹아있는 경우
# 시작할 때 한번 녹으니까 다 사라진 경우

if sum([sum(i) for i in maps]) in [0, 1]:
    print("0")
    exit()

visited = [[False] * m for _ in range(n)]

# 녹이기
tmp = copy.deepcopy(maps)
for i in range(n):
    for j in range(m):
        if maps[i][j] != 0:
            go(i, j)
maps = copy.deepcopy(tmp)

sum_maps = sum([sum(i) for i in maps])
if sum_maps == 0 or sum_maps == 1:
    print(result)
    exit()

    # 덩어리 찾기
cur = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] != 0 and not visited[i][j]:
            cur += 1
            bfs(i, j)
            if cur > 1:
                print(result)
                exit()

result += 1

while True:
    visited = [[False] * m for _ in range(n)]
    result += 1
    # 녹이기
    tmp = copy.deepcopy(maps)
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 0:
                go(i, j)
    maps = copy.deepcopy(tmp)

    sum_maps = sum([sum(i) for i in maps])
    if sum_maps == 0 or sum_maps == 1:
        print(0)
        break


    # 덩어리 찾기
    cur = 0
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 0 and not visited[i][j]:
                cur += 1
                bfs(i, j)
                if cur > 1:
                    print(result)
                    exit()

 

풀이 방법

1. go 함수 : map을 돌며 상하좌우 0 개수만큼 현재 칸을 빼줌

2. bfs 함수 : map을 돌며 분리된 빙산이 있는지 확인 (visited)

주의해야 할 점

1. 시작할 때 부터 전부 녹아있는 경우

2. 시작할 때 한번 녹으면 다 사라지는 경우

3. 모두 녹을 때 까지 분리되지 않는 경우

 

반례

5 5
0 0 0 0 0
0 0 10 10 0
0 10 0 10 0
0 0 10 10 0
0 0 0 0 0

정답 : 0
출력 : 1

 

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0