백준 / 빙산 / 2573번 / Python

*문제 출처는 백준에 있습니다.

 

문제 제목: 빙산 / 2573번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/2573

 

문제 설명

---

나의 풀이

import sys
from collections import deque


input = sys.stdin.readline


def solution(n, m, ice):
    answer = 0
    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    # 빙산이 있는 좌표만 저장
    ice_coords = [(i,j) for i in range(n) for j in range(m) if ice[i][j] > 0]

    while True:
        # 1. 빙산 덩어리 수 세기 (BFS)
        visited = [[False]*m for _ in range(n)]
        chunks = 0

        for i, j in ice_coords:
            if not visited[i][j]:
                chunks += 1
                if chunks >= 2:
                    return answer

                q = deque()
                q.append((i,j))
                visited[i][j] = True

                while q:
                    y, x = q.popleft()
                    for dy, dx in directions:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < n and 0 <= nx < m:
                            if not visited[ny][nx] and ice[ny][nx] > 0:
                                visited[ny][nx] = True
                                q.append((ny, nx))

        if chunks == 0:
            return 0

        # 2. 녹을 양 계산
        melt = [[0]*m for _ in range(n)]
        for y, x in ice_coords:
            sea = 0
            for dy, dx in directions:
                ny, nx = y+dy, x+dx
                if 0 <= ny < n and 0 <= nx < m and ice[ny][nx] == 0:
                    sea += 1
            melt[y][x] = sea

        # 3. 얼음 녹이기 & 얼음 있는 좌표 업데이트
        new_ice_coords = []
        for y, x in ice_coords:
            ice[y][x] = max(0, ice[y][x] - melt[y][x])
            if ice[y][x] > 0:
                new_ice_coords.append((y,x))

        ice_coords = new_ice_coords
        answer += 1


def main():
    n, m = map(int, input().split())
    ice = [list(map(int, input().split())) for _ in range(n)]
    print(solution(n, m, ice))


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

def solution(n, m, ice):
    answer = 0
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 우 좌 하 상

    while True:
        # 1. 빙산 녹는 양 계산
        visited = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                if ice[i][j] > 0:
                    for dy, dx in move:
                        ny, nx = i + dy, j + dx
                        if 0 <= ny < n and 0 <= nx < m:
                            if ice[ny][nx] == 0:
                                visited[i][j] += 1

        # 2. 빙산 녹이기 적용
        for i in range(n):
            for j in range(m):
                ice[i][j] = max(0, ice[i][j] - visited[i][j])

        # 3. 빙산 덩어리 수 세기 (BFS)
        count = 0
        checked = [[False] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                if ice[i][j] > 0 and not checked[i][j]:
                    count += 1
                    if count >= 2:
                        return answer + 1

                    # BFS 시작
                    q = deque()
                    q.append((i, j))
                    checked[i][j] = True

                    while q:
                        y, x = q.popleft()
                        for dy, dx in move:
                            ny, nx = y + dy, x + dx
                            if 0 <= ny < n and 0 <= nx < m:
                                if ice[ny][nx] > 0 and not checked[ny][nx]:
                                    q.append((ny, nx))
                                    checked[ny][nx] = True

        # 4. 전부 다 녹았는지 체크
        if all(ice[i][j] == 0 for i in range(n) for j in range(m)):
            return 0

        answer += 1

위는 시간초과가  발생하는 알고리즘입니다!