[Python] 백준 2573 - 빙산 [Gold4]

출처

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

풀이 전략

[백준 2636 - 치즈] https://www.acmicpc.net/problem/2636

2024.09.10 - [Baekjoon] - [C++] 백준 2636 - 치즈 [Gold4]

[C++] 백준 2636 - 치즈 [Gold4]

이 문제와 상당히 유사한 방식으로 접근을 해야 한다.
다만 다른 점은, 이 문제에서는 빙산이 둘로 쪼개지는 순간의 시간을 출력해야 하기 때문에 BFS 또는 DFS로 탐색을 하면서 빙산의 존재를 확인하고 그 과정에서 check 함수를 별도로 선언해서 빙산이 2개 이상으로 나뉘어 졌는지를 확인하는 과정을 추가해야 한다.

풀이

왼쪽의 과정은 문제에서 주어진 예시를 시각화한 과정으로, 하늘색 형광펜이 빙산과 맞닿아 있는 바닷물로 하늘색 형광펜의 개수만큼 (i,j)에서 빼줘야하고 파란색 형광펜은 빼준 뒤의 빙산을 표시한 것이다.

이 문제에서 melt와 check 함수 2개를 정의 했는데, 설명은 그림에 적어 두었지만 조금 더 자세히 설명을 하자면 다음과 같다.

melt

먼저 melt함수의 경우 주된 목적은 빙하가 녹는 것을 표기하는 함수이다.

def melt():
    new_ice = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if ice[i][j]:
                cnt = 0
                for k in range(4):
                    ni, nj = i + dx[k], j + dy[k]
                    if 0 <= ni < N and 0 <= nj < M and not ice[ni][nj]:
                        cnt += 1
                new_ice[i][j] = max(0, ice[i][j]-cnt)
    return new_ice

이 함수를 보면 new_ice라는 기존의 ice 배열과 똑같은 크기의 0으로 채워진 배열을 정의한다. 그 뒤 배열을 탐색하면서 빙하인 경우 cnt를 선언한 뒤 빙하 다음의 좌표 (n_i, n_j)가 빙하가 아닌 경우 (바닷물인 경우) cnt를 늘려주고 그 cnt 만큼을 ice[i][j]에서 빼준 값을 새로 정의한 배열에 적어두고 그 배열을 return하는 과정으로 이루어진다.
이를 통해 return된 new_ice 배열에는 1년이 지난 뒤 녹고 남은 빙하에 대한 정보만 남아있게 된다.

check

두 번째로 check 함수의 경우 주된 목적은 빙하가 녹은 뒤 둘 이상으로 나뉘어졌는지를 확인하는 것이다.

def check():
    visited = [[0]*M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if ice[i][j] and not visited[i][j]:
                bfs(i, j, visited)
                cnt += 1
    return cnt

여기서는 방문하지 않은 빙하를 BFS로 탐색을 하면서 cnt를 늘려주는데, 이 cnt가 0이면 빙하가 존재하지 않는 경우, 1이면 빙하가 하나의 덩어리로 존재하는 경우, 2 이상이면 빙하가 둘 이상으로 쪼개진 경우를 의미한다.

year = 0
while True:
    cnt = check()
    if cnt >= 2: # 빙하가 분리된 경우
        print(year)
        break
    if cnt == 0: # 빙하가 없는 경우
        print(0)
        break
    ice = melt() 
    year += 1

그 뒤 무한반복문을 돌면서 check 함수를 거쳐 반환된 cnt에 따라 year를 출력할지 0을 출력할지 그도 아니면 1년 더 기다리면서 빙하가 녹는 것을 기다릴지를 결정한다.

소스 코드

# Question: BJ 2573 (https://www.acmicpc.net/problem/2573)
# Rank: Gold4
# Algorithm: Implementation, Graph, DFS, BFS

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y, visited):
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 내에 있고 (nx,ny)가 빙하이면서 방문하지 않았다면
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and ice[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = 1
                
def melt():
    new_ice = [[0] * M for _ in range(N)] # 녹은 빙하의 정보를 담을 배열
    for i in range(N):
        for j in range(M):
            if ice[i][j]: # 빙하인 경우
                cnt = 0
                for k in range(4):
                    ni, nj = i + dx[k], j + dy[k]
                    # ni, nj가 범위 내에 있고 빙하가 아닌 경우
                    if 0 <= ni < N and 0 <= nj < M and not ice[ni][nj]:
                        cnt += 1 # 녹은 빙하이기 때문에 cnt를 1 증가시킴
                new_ice[i][j] = max(0, ice[i][j]-cnt) # 녹은 빙하의 수를 저장
    return new_ice

def check():
    visited = [[0]*M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            # 빙하이고 방문하지 않았다면
            if ice[i][j] and not visited[i][j]:
                bfs(i, j, visited) # bfs로 확인
                cnt += 1
    return cnt

year = 0
while True:
    cnt = check()
    if cnt >= 2: # 빙하가 분리된 경우
        print(year)
        break
    if cnt == 0: # 빙하가 없는 경우
        print(0)
        break
    ice = melt() 
    year += 1

여기서 조금 특이한 점은 sys.setrecursionlimit(10**6) 이 코드를 추가한 점이다. 그 이유는 이 문제를 처음 풀 때 BFS가 아니라 DFS로 풀었었는데, 그렇게 하게 될 경우 답은 제대로 출력이 되지만, DFS의 기본 알고리즘이 재귀를 이용하는 것이기 때문에 제출을 했을 때 RecursionError가 발생했다. 왜 그런지 모르겠어서 GPT에게 물어보니 재귀로 인한 스택오버플로우의 가능성이 있다는 답변을 받아서 재귀의 limit을 10의 6제곱으로 제한을 걸어두면 RecursionError는 발생하지 않는다고 한다.
그러나 그렇게 해도 시간초과가 떠서 결국 BFS로 풀었다.

참고용으로 기존에 풀었던 DFS 풀이를 첨부한다.

# Question: BJ 2573 (https://www.acmicpc.net/problem/2573)
# Rank: Gold4
# Algorithm: Implementation, Graph, DFS, BFS

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(x, y, visited):
    visited[x][y] = 1
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and ice[nx][ny]:
            dfs(nx, ny, visited)
            
def melt():
    new_ice = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if ice[i][j]:
                cnt = 0
                for k in range(4):
                    ni, nj = i + dx[k], j + dy[k]
                    if 0 <= ni < N and 0 <= nj < M and not ice[ni][nj]:
                        cnt += 1
                new_ice[i][j] = max(0, ice[i][j]-cnt)
    return new_ice

def check():
    visited = [[0]*M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if ice[i][j] and not visited[i][j]:
                dfs(i, j, visited)
                cnt += 1
    return cnt

year = 0
while True:
    cnt = check()
    if cnt >= 2:
        print(year)
        break
    if cnt == 0:
        print(0)
        break
    ice = melt()
    year += 1

혹시 DFS 코드를 사용하면서 시간초과와 RecursionError를 발생시키지 않는 풀이법이 있으신 분들 힌트나 조언을 주시면 감사드립니다🙏🏻

결과