[백준] 2573번 빙산 ★

💡문제접근

• BFS 탐색 알고리즘을 사용해서 문제를 해결했다.
• Python3로 제출했더니 시간초과(TLE)가 나와서 PyPy3로 제출했더니 AC를 받았다. 시간초과를 해결하는 방법은 잘 모르겠다...

💡코드(메모리 : 220212KB, 시간 : 804ms)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
iceberg = [list(map(int, input().strip().split())) for _ in range(N)]

def BFS(a, b):
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # 만약 빙산의 인접한 구역이 바닷물이 아니라면?
                if iceberg[nx][ny] != 0:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                # 만약 빙산의 인접한 구역이 바닷물이라면?
                # 나중에 인접한 구역의 바닷물 수만큼 차감해줘야하므로 바닷물 2차원 배열에 값을 저장
                else:
                    sea[x][y] += 1

year = 0
while True:
    visited = [[False] * M for _ in range(N)]
    sea = [[0] * M for _ in range(N)]
    # 빙산이 녹았을 때 분리되어 생성되는 섬의 개수
    li = []
    for i in range(N):
        for j in range(M):
            if iceberg[i][j] != 0 and not visited[i][j]:
                li.append(BFS(i, j))

    for i in range(N):
        for j in range(M):
        	# 빙산의 높이를 바닷물 2차원 배열의 값만큼 빼줌
            iceberg[i][j] -= sea[i][j]
            # 만약 음수값이 나오면 전부 0으로 선언
            if iceberg[i][j] < 0:
                iceberg[i][j] = 0
	
    if len(li) == 0 or len(li) >= 2:
        break
    else:
        year += 1

if len(li) >= 2:
    print(year)
else:
    print(0)

💡문제접근