[백준] 2573 빙산 풀이 Python

문제로 이동

---

이번 글에서는 문제에 대한 설명과 풀이보다 골드 난이도임에도 불구하고 무려 11WA를 받게된 이유, 그리고 드디어 Solved 할 수 있었던 이유를 찾고 포스팅 했습니다.

혹시 "맞는데 왜 틀려" 늪에 빠져있다면 이 글을 보았을 때 도움이 될 수 있습니다😀

---

과거의 흔적

틀렸던 이유

1. RecursionError

Python의 경우 재귀 함수의 깊이가 1000으로 고정되어 있습니다.

만약 1000번보다 더 큰 재귀를 돌기 위해선 Recursion을 설정해줘야 합니다.

5개월 전 당시엔 이를 DFS로 풀다가 놓쳤던 것 같네요

2. 시간초과 및 틀렸습니다

과거의 코드를 보니 빙산이 분리되는 구간에서 줄일 수 있는 로직이 보였고, 애초에 너무 복잡하게 생각을 했는지 코드가 직관적이지 못합니다 ㅠㅠ 그리고 빙산을 녹이고 즉각 반영하는 것이 아닌 후처리를 해야 하는데 이 부분을 놓쳤습니다.

3. 다시 풀었는데 3WA

녹은 빙하만큼 field에 후처리를 하고 한번에 반영해주는 로직을 선택했는데, 이 과정에서 field의 일부 값이 음수가 되어버리는 케이스를 목격했습니다. 음수가 되면 BFS를 할 때 물로 인식을 하지 않기 때문에(물은 0이므로) Wrong Answer을 받았습니다.

맞았던 이유

1. 빙산이 갈라지면 해당 년(year)을 반환한다
2. 빙산이 갈라지지 않는 경우엔 0을 반환한다.
   1. 애초에 빙산이 없다(모두 물이다)
   2. 필드에 빙산을 녹일 물이 없다? (이 경우는 테스트 케이스에 없으며 필드에 반드시 물이 존재합니다)
   3. 갈라지지 않고 모두 녹아버리는 경우

---

소스코드

Python3

 

from collections import deque
N,M = map(int,input().split())
field = []
iceblock = deque()
direction = [[0,1],[1,0],[-1,0],[0,-1]]
for i in range(N):
    line = list(map(int,input().split()))
    field.append(line)
    for j in range(len(line)):
        if line[j]!=0:
            iceblock.append([j,i])

# 1. 빙산 분리 체크
def checkBreakIce():
    visited = [[0]*M for _ in range(N)]
    dq = deque()
    cnt = 0
    for ix,iy in iceblock:
        if visited[iy][ix]==1:continue
        cnt+=1
        if cnt>=2:
            return True #분리되면 True 반환
        dq.append([ix,iy])
        while dq:
            x,y = dq.popleft()        
            for dx,dy in direction:
                nx,ny = dx+x,dy+y
                if 0>nx or 0>ny or M<=nx or N<=ny or field[ny][nx]==0:continue
                if visited[ny][nx]==1:continue
                visited[ny][nx]=1
                dq.append([nx,ny])            
    return False

#2. 빙산의 녹음
def melting():
    size = len(iceblock)
    sumfield = [[0]*M for _ in range(N)]
    for i in range(size):
        x,y = iceblock.popleft()
        water_cnt = 0
        for dx,dy in direction:
            nx,ny = x+dx, y+dy
            if 0>nx or 0>ny or M<=nx or N<=ny or field[ny][nx]!=0:continue
            water_cnt+=1
        sumfield[y][x]-=water_cnt
        if field[y][x]-water_cnt>0:#아직 빙산이 덜녹았다면
            iceblock.append([x,y])  #다시 빙산 리스트에 추가

    for i in range(N):
        for j in range(M):
            if field[i][j] + sumfield[i][j] < 0:
                field[i][j]=0
            else:
                field[i][j] += sumfield[i][j]

def solution():
    year = 1
    while True:
        melting()
        if not iceblock:#빙산이 이미 모두 녹았거나 갈라졌다면
            return 0
        if  checkBreakIce():
            return year
        year+=1
    return 0
print(solution())

덱(deque)을 쓴 이유

남아있는 빙하를 체크하기 위해 list를 사용했습니다. 이 과정에서 left remove와 right append가 빈번히 일어나기 때문에 deque를 사용했습니다.