[백준알고리즘] 2573번: 빙산 -Python

[백준알고리즘] 2573번: 빙산 -Python

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

2573번: 빙산

이 코드는 PyPy3로만 통과한 코드다. Python3로는 시간 초과가 발생한다.

 

사실 처음에 이렇게 코드를 작성하려고 하지는 않았었다... 하지만 머리가 귀찮다고 파업을 하는 바람에 이렇게만 우선 풀게 되었다..... 원래대로 풀면 Python3의 시간 초과 문제도 해결할 수 있을 것이다.

 

PyPy3로 통과한 코드는 매번 지도를 검사했다. 그러다가 빙산이 발견되면 거기서부터 BFS를 돌렸다. BFS덩어리가 두개 나오게 되면 year를 출력하고, BFS덩어리가 나오지 않으면 0을 출력한다.

BFS덩어리가 하나만 나오게 된다면 BFS를 돌릴때 주변의 바다의 개수도 같이 검사해주었기 때문에 둘러싸인 바다의 수만큼 높이를 감소시켜주도록 했다.

그리고 또 지도 전체를 검사하면서 같은 동작을 반복하는 간단한 코드가 완성된다.

 

처음에 '이렇게 풀면 되겠네!' 했던 코드는 조금 더 복잡?할 거다. 사실 별 차이 없을 텐데 귀찮았다.... 풀어야지 하는 마음보다 쉬고 싶다는 마음이 간절했던.. 아래 코드와는 직접적으로 관련은 없기 때문에 접어두겠다.

아무튼 생각했던 방법은 처음에 빙산의 위치를 다 찾아놓으면 더이상 빙산이 늘어나지는 않기 때문에 이 안에서만 반복하는 것이었다. 매년 존재하는 빙산의 위치만 돌면서, 그 빙산 주변의 바다의 개수만 검사해준다. 여기서 바로 감소시키면서 돌리는 게 아니라 먼저 감소할 양을 검사하기만 하면서 돈다.

이후 모든 빙산의 주변 바다 개수를 확인한 다음에 감소량만큼 높이들을 감소시켜준다. 반복문을 돌면서 감소시키지 않는 이유는 검사중인 년도에 바다가 되어버린 부분은 같은 년도의 빙산들에게는 높이 감소에 영향을 주지 않기 때문이다.

그러고 나서 이제 하나의 빙산에서 BFS로 모든 빙산 좌표에 도달할 수 있는지를 검사하는 것이었다.

 

이렇게 하면 매번 모든 지도를 검사하는 것이 아니고 빙산들의 좌표만 확인하면 되는 것이기 때문에, 처음에 구한 빙산의 좌표를 큐를 사용해 빼고 넣는 방법으로 남아있는 빙산들만 유지를 한다면 시간 복잡도를 크게 줄일 수 있을 것이다.

from collections import deque
from sys import exit

n, m = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

def bfs(i, j):
    rtn = []
    queue = deque([(i, j)])
    visited[i][j] = True

    while queue:
        qi, qj = queue.popleft()
        c = 0
        for d in range(4):
            x, y = qi+dx[d], qj+dy[d]
            if 0<=x<n and 0<=y<m and not visited[x][y]:
                if iceberg[x][y] == 0:
                    c += 1
                else:
                    visited[x][y] = True
                    queue.append((x, y))
        rtn.append((qi, qj, c))
    return rtn

year = 0
while True:
    #check
    visited = [[False]*m for _ in range(n)]
    ice = deque()
    cnt = 0
    for i in range(1, n-1):
        for j in range(1, m-1):
            if iceberg[i][j] > 0 and not visited[i][j]:
                cnt += 1
                if cnt > 1:
                    print(year)
                    exit()
                ice.extend(bfs(i, j))

    if cnt == 0:
        year = 0
        break

    year += 1

    #녹이기
    while ice:
        i, j, h = ice.popleft()
        iceberg[i][j] = max(0, iceberg[i][j]-h)

print(year)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다