[Python][백준] 2573번 빙산

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

공부 날짜 : 2023.02.07
정답 참조 여부 : X

빙산이 바다에 닿은 부분만큼 녹게된다.(4방향에서 바다와 닿은 방향의 수만큼 녹는다.)
이 때 빙산이 2덩어리로 나뉘어 지는 시점을 구하되 나뉘어 지지 않고 한덩어리로 다 녹게되면 0을 출력하는 문제이다.

---

얼음을 녹는걸 구현하는건 모든칸을 돌면서 해당칸이 얼음일 때 주변 4칸에 바다가 있는 면을 확인하여 얼음을 녹게 하였다.

옛날이였으면 그냥 바다에 바로 얼음을 녹였겠지만, 바로 녹이면서 탐색을 할경우

0 0 0 0 0
0 2 4 2 0
0 0 0 0 0

의 결과는

0 0 0 0 0
0 0 2 0 0
0 0 0 0 0

이지만,

녹이면서 탐색을 하게되면

0 0 0 0 0
0 0 4 2 0
0 0 0 0 0

상태에서 4를 탐색할 때 바다의 수를 3으로 카운팅 하기 때문에, 의도한 바와 다르게 녹게된다.

그래서 새로운 배열을 만들고, 얼음이 녹고 남은 양을 새로운 배열에 넣어주는 방식으로 해결했다.

---

또한, 얼음 덩어리의 개수를 구하는 방법은 마찬가지로 모든 칸을 돌면서 얼음을 만났을 때 개수를 세주고 같은 덩어리인 얼음을 bfs탐색으로 모두 0 처리해 주었다.

그 결과 1이면 다시 녹이고 0이면 0출력 2이면 년도 출력 으로 코드를 작성했다.

---

결과는 시간초과...... 솔직히 아무리해도 시간을 더 줄일 방법을 모르겠어서 PyPy3로 제출했더니 정답으로 나왔다.

Python3로 제출했을 때 정답인 코드를 만들고 싶지만, 내 실력으로는 한계인거 같다.

소스코드

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

###############################################
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
###############################################
# 빙산이 녹은 결과를 반환하는 함수
def Melt_ice():
    # 새로 저장된 녹은 얼음
    new_ice = [[0 for _ in range(m)] for _ in range(n)]

    # 모든 칸에 대해서
    for x in range(n):
        for y in range(m):
            # 바다이면 수행 안함
            if ice_map[x][y] == 0:
                continue

            # 주변의 바다인 칸의 개수
            count = 0
            # 주변 4칸에 대해서
            for dir in range(4):
                nx = x + dx[dir]
                ny = y + dy[dir]

                # 범위 벗어나면 체크 안함
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue

                # 바다이면 개수 추가
                if ice_map[nx][ny] == 0:
                    count += 1

            # 새로 녹은 배열에 녹은 얼음의 크기를 저장
            # 만약 음수면 0으로 저장
            new_ice[x][y] = ice_map[x][y] - count if ice_map[x][y] > count else 0

    return new_ice


###############################################
# 빙산의 개수를 반환하는 함수
def Count_ice():
    # 기존의 얼음에 영향을 미치지 않기 위한 deepcopy
    new_ice = deepcopy(ice_map)

    # 얼음 덩어리의 개수
    count_ice = 0

    # 모든칸에 대해서
    for x in range(n):
        for y in range(m):
            # 바다이면 체크안함
            if new_ice[x][y] == 0:
                continue

            # 얼음이면 개수 추가
            count_ice += 1

            # 현재 위치를 기준으로 주변 모든 얼음은 한덩어리 이므로
            # 주변을 탐색하며 같은 덩어리인 얼음은 0으로 만들어 줌
            visit = deque()
            visit.append((x, y,))
            while visit:
                vx, vy = visit.popleft()
                new_ice[vx][vy] = 0

                for dir in range(4):
                    nx = vx + dx[dir]
                    ny = vy + dy[dir]

                    # 범위 이내이며, 해당칸이 얼음일때(0이 아닐때)
                    # 0 처리후 방문가능위치 추가
                    if 0 <= nx < n and 0 <= ny < m and new_ice[nx][ny]:
                        # new_ice[nx][ny] = 0
                        visit.append((nx, ny,))

    return count_ice


###############################################
# 연산 시작
n, m = map(int, input().split())

ice_map = [list(map(int, input().split())) for _ in range(n)]

year = 0

while True:
    # 빙산의 개수를 세고
    count = Count_ice()

    # 두 덩어리로 나뉘어지면 년도 출력후 반복 종료
    if count >= 2:
        print(year)
        break

    # 한번에 0이 되면 0 출력후 반복 종료
    elif count == 0:
        print(0)
        break

    # 1년 후 얼음이 녹는다.
    year += 1
    ice_map = Melt_ice()