파이썬으로 풀어보는 백준 2573번: 빙산

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

2573번: 빙산

 

 

내 풀이:

def check(y, x):
    global N, M
    cnt = 1
    visited = [[False] * M for _ in range(N)]
    visited[y][x] = True
 
    s = [(y, x)]
 
    while s:
        y, x = s[-1]
 
        for dir in range(4):
            ny = y + dy[dir]
            nx = x + dx[dir]
 
            if not visited[ny][nx] and arr[ny][nx] != 0:
                s.append((ny,nx))
                visited[ny][nx] = True
                cnt += 1
                break
 
        else:
            s.pop()
    return cnt
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
melt = [[0] * M for _ in range(N)]
dy = [-1, 0 , 1, 0]
dx = [0, 1, 0, -1]
 
ice = []
for i in range(N):
    for j in range(M):
        if arr[i][j] != 0:
            ice.append((i, j))
 
ans = 0
cnt = 0
while ice:
    if len(ice) != check(ice[0][0], ice[0][1]):
        ans = cnt
        break
    cnt += 1
 
    for i in range(len(ice) - 1, -1, -1):
        y, x = ice[i]
        m = 0
 
        for dir in range(4):
            ny = y + dy[dir]
            nx = x + dx[dir]
 
            if arr[ny][nx] == 0:
                melt[y][x] += 1
 
    for i in range(len(ice) - 1, -1, -1):
        y, x = ice[i]
        if arr[y][x] - melt[y][x] <= 0:
            arr[y][x] = 0
            ice.pop(i)
        else:
            arr[y][x] -= melt[y][x]
 
        melt[y][x] = 0
 
print(ans)

PyPy3, 692ms

Python3, 시간 초과

처음 실수한 부분은 각 지점에서 얼음이 녹는 양을 계산하고 계산한 그 즉시 얼음을 녹였더니 녹은 자리가 0이 되는 경우 그 옆 얼음에서 0이 하나 더 있다고 인식하여 얼음이 조건보다 더 빠르게 녹았다.

 

 

def check(y, x):
    global N, M
    cnt = 1
    visited = [[False] * M for _ in range(N)]
    visited[y][x] = True
 
    s = [(y, x)]
 
    while s:
        y, x = s.pop()
 
        for dir in range(4):
            ny = y + dy[dir]
            nx = x + dx[dir]
 
            if not visited[ny][nx] and arr[ny][nx] != 0:
                s.append((ny,nx))
                visited[ny][nx] = True
                cnt += 1
 
    return cnt
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
melt = [[0] * M for _ in range(N)]
 
dy = [-1, 0 , 1, 0]
dx = [0, 1, 0, -1]
 
ice = []
for i in range(1, N-1):
    for j in range(1, M-1):
        if arr[i][j] != 0:
            ice.append((i, j))
 
ans = 0
cnt = 0
while ice:
    if len(ice) != check(ice[0][0], ice[0][1]):
        ans = cnt
        break
    cnt += 1
    melt_co = []
    for i in range(len(ice) - 1, -1, -1):
        y, x = ice[i]
 
        for dir in range(4):
            ny = y + dy[dir]
            nx = x + dx[dir]
 
            if arr[ny][nx] == 0:
                melt[y][x] += 1
 
        if melt[y][x] > 0:
            melt_co.append((y, x, i))
 
    for y, x, i in melt_co:
        arr[y][x] -= melt[y][x]
        if arr[y][x] <= 0:
            arr[y][x] = 0
            ice.pop(i)
 
        melt[y][x] = 0
 
print(ans)

Python3, 4244ms

PyPy3, 520ms

시간 초과의 원인은 2가지가 있었다. 첫 번째로 빙하의 연결 상태를 dfs로 탐색할 때 발생했는데 정석적인 방법은 stack에 탐색순서가 남도록 하는 것이다. 때문에 이전 코드에서는 주변을 탐색했을 때 새로 추가할 얼음이 없으면 그제야 pop을 해주었는데 이 과정에서 stack에 많은 양에 데이터가 쌓이면서 시간 지연이 발생하였다. stack 정보를 사용할 일이 없고 얼음만 전체 탐색해주면 되기 때문에 마지막 좌표를 가져오는 것에서 바로 pop하는 것으로 수정해주었다. 또한 1이라도 녹는 얼음은 melt_co라는 리스트에 좌표를 저장해주어 얼음이 녹는 처리를 좀 더 빠르게 해주었다. 만약 298*298 의 빙하가 있다면 88804개의 빙하중 1188개의 빙하만이 녹는데 모든 빙하에 대해 탐색하는 것은 시간 지연의 원인이 될 것이라 생각하였다.