[백준] 2573 : 빙산

 

2573번: 빙산

백준의 빙산 문제는 dfs나 bfs를 이용하여 풀수있는 문제다.

실제로 해당 개념을 활용하여 약 30분내로 문제를 다 풀었지만, 결과는 처참했다. 계속해서 런타임 or 시간초과가 뜨고 시간을 최대한 줄이기위해 재귀대신 반복문으로 사용하고, 가지치기를 하면서 시간을 줄이기 위해 노력했다. 하지만 4시간 가까이 수정했음에도 10번이 넘도록 시간초과가 뜬다..ㅠㅠ

혹시나 python3보다 더 빠른 pypy3로 돌려봤더니 단번에 성공하는걸보고

python과 pypy의 차이를 다시한번 느꼈다.

해당 코드는 pypy로만 통과가 되고, 계속해서 수정하면서 python으로 통과시켜보도록 하겠다.

from collections import deque
import sys
dx = [-1, 1, 0, 0]  # 상하우좌
dy = [0, 0, 1, -1]

def bfs(x,y):
    global ice
    q = deque()
    q.append([x,y])
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        minus[(x, y)] = 0
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<n and 0<=ny<m:
                if ice[nx][ny] == 0:    # 빙산이 없는경우 +1 해준다
                    minus[(x, y)] += 1
                elif ice[nx][ny] != 0 and visited[nx][ny] == 0:  # 빙산인데 방문하지 않을경우 append시켜줌
                    q.append([nx,ny])
                    visited[nx][ny] = 1
    return minus
n, m = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(n)]
year = 0
stan = n*m
while True:
    # step1. 빙하가 없으면 바로 종료
    res = 0
    for row in ice:
        res += row.count(0)
    if res == stan:
        print(0)
        sys.exit()

    # step2. 빙산 조사 시작
    island = 0
    minus = dict()
    visited = [[0] * m for _ in range(n)]
    for i in range(1, n-1):
        for j in range(1, m-1):
            if ice[i][j] != 0 and visited[i][j] == 0:
                bfs(i, j)
                island += 1
                print(minus)
                # 두덩어리가 되는 순간 year 출력후 종료
                if island == 2:
                    print(year)
                    sys.exit()
    # step3. 빙산 녹이기
    for key, value in minus.items():
        ice[key[0]][key[1]] -= value
        if ice[key[0]][key[1]] < 0:
            ice[key[0]][key[1]] = 0

    # step4. 빙산을 다 녹이고 난뒤 1년 추가
    year += 1