[파이썬] 백준 16933 : 벽 부수고 이동하기 3 (골드1)

[파이썬] 백준 16933 : 벽 부수고 이동하기 3 (골드1)

16933번: 벽 부수고 이동하기 3

---

문제

---

풀이

방향성 생각

• 벽뿌2랑 동일한 문제.
• 다른 점이 있다면, 큐에 낮과 밤 정보를 넣어줘야 해서 메모리 관리가 조금 더 빡빡한 점.

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,skill = map(int,input().split())
arr = [list(map(lambda x: int(x), list(input()))) for _ in range(h)]

inf = 1e7+1
visit = [[[inf]*w for _ in range(h)] for _ in range(skill+1)]

dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit[0][0][0] = 1
q = deque([(0,0,0,1,False)])
while q:
    x,y,s,t,night = q.popleft()
    
    if t <= visit[s][y][x]:
        for dx,dy in dire:
            nx,ny,ns,nt = x+dx,y+dy,s+1,t+1
    
            if 0<=nx<w and 0<=ny<h:
                if not arr[ny][nx] and nt < visit[s][ny][nx]:
                    visit[s][ny][nx] = nt
                    q.append((nx,ny,s,nt,night^1))
                elif arr[ny][nx] and s < skill and nt < visit[ns][ny][nx]:
                    if night:
                        visit[ns][ny][nx] = nt+1
                        q.append((nx,ny,ns,nt+1,night))
                    else:
                        visit[ns][ny][nx] = nt
                        q.append((nx,ny,ns,nt,night^1))
                        
answer = min(visit[i][-1][-1] for i in range(skill+1))
print(-1) if answer == inf else print(answer)

• 밤일 때 다음 칸이 1인 경우, 한 턴을 기다린 후 이동해야하므로 시간이 2초가 소비된다.
• 시간 초과를 해결하는 가장 중요한 점은, 특정 노드에 접근하는 큐들이 엄청 쌓여있다는 것을 인지하고 해결하는 것이다.
• 이미 visit에 갱신이 되어있는 정보임에도 불구하고 for문으로 인접 노드들에 대해서 모두 순회를 하면 안된다.

코멘트

.