[백준] 2573 빙산 - 파이썬 [골드4]

지속적으로 코딩테스트 준비를 하면서 풀었던 문제인데, 생각보다 빨리 구현하여 기억하고자 올립니다 :)

2573번: 빙산

---

문제

백준 문제

---

풀이

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

maps = [list(map(int, input().split())) for _ in range(N)] # 빙산 지도
dx = [-1, 1, 0, 0] # 4방향
dy = [0, 0, -1, 1]
year = 0 # 년수


def count_ice(check_ice): # 붙어있는 얼음갯수 체크
    cnt = 0
    visited = [[0] * M for _ in range(N)]
    q = deque()
    for x, y in check_ice:
        if not visited[x][y]:
            q.append((x, y))
            while q:
                x, y = q.popleft()
                visited[x][y] = 1
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < N and 0 <= ny < M:
                        if maps[nx][ny] > 0 and not visited[nx][ny]:
                            visited[nx][ny] = 1
                            q.append((nx, ny))
            cnt += 1

    if cnt >= 2: # 두 덩어리 이상이면 True
        return True
    else:
        return False


while True:
    maps_ice = [[0] * M for _ in range(N)] # 주변의 0의 갯수를 담을 map
    check_ice = [] # 0 이상의 숫자가 존재하면 체크해야할 부분이라 판단한 데이터를 담을 곳
    for i in range(N):
        for j in range(M):
            if maps[i][j] > 0:
                check_ice.append((i, j))  # 체크해야할 ice

    if len(check_ice) == 0: # 체크해야할 ice가 없으면 0을 return
        year = 0
        break
    if count_ice(check_ice): # 얼음덩어리를 갯수를 체크한다.
        break

    for x, y in check_ice:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if maps[nx][ny] <= 0:
                    maps_ice[x][y] += 1  # 얼음 주변의 0의 개수 카운트

    for x, y in check_ice:  # 얼음 주변의 0의 갯수만큼 감소
        maps[x][y] -= maps_ice[x][y]
    year += 1

print(year if year > 0 else 0)

 

참고로 시간초과로 인해서 PyPy3 를 사용하였습니다.