백준 2573_빙산

빙산(백준 2573)

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

세부 구현과 최적화에서 맥을 못춘 문제였다…
예제를 통과한 것 까지는 좋았으나
결국 시간초과가 나버렸고
이후 코드를 고치려 여러 블로그를 전전하였지만
기본적으로 BFS 방식으로 푼 코드들과 접합하려다
오히려 좋지 않은 결과만 낳았다

결국은 GPT에게 코드를 최적화하는 방향을 요청하였고,
이에 맞게 수정하여 통과하였다

Code

import sys
from collections import deque
sys.setrecursionlimit(10**8)

inp = sys.stdin.readline

boardX, boardY = map(int, inp().split())
board = [list(map(int, inp().split())) for _ in range(boardX)]

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

# DFS로 빙하 녹이는 함수
def meltIceberg(startX, startY, visit):
    nearZeroCount = 0

    for i in range(4):
        nx, ny = startX + dx[i], startY + dy[i]
        if 0 <= nx < boardX and 0 <= ny < boardY and not visit[nx][ny]:
            if board[nx][ny] == 0:
                nearZeroCount += 1
            else:
                visit[nx][ny] = True
                meltIceberg(nx, ny, visit)

    board[startX][startY] = max(0, board[startX][startY] - nearZeroCount)

# '빙하 덩어리' 확인 함수
def checkIceberg():
    visit = [[False] * boardY for _ in range(boardX)]
    count = 0

    for i in range(boardX):
        for j in range(boardY):
            if board[i][j] != 0 and not visit[i][j]:
                count += 1
                visit[i][j] = True
                meltIceberg(i, j, visit)

    return count

time = 0
while True:
    remaining_icebergs = checkIceberg()

    if remaining_icebergs == 0:
        print(0)
        break

    if remaining_icebergs >= 2:
        print(time)
        break

    time += 1

해결 아이디어

1. DFS를 통해 빙하를 녹임
   이 때, ‘바로’ 녹이는 것이 아니라,
   개수를 저장한 후, 바깥에서 녹여준다
   
2. checkIceberg()를 통해 빙하를 확인하며,
   ‘동시에’ 녹여준다
   
3. 남은 빙하의 개수를 확인하고 조건에 맞게 출력해준다