N,M,K로 visit 배열 만드는 하위 골드 문제의 경우 map size가 굉장히 작았다.
V[K][N][M]으로 BFS를 진행하는 경우, K값이 커서 불가능
V[N][M]으로 줄여서 최적화를 하는 테크닉 필요
방문 유무와 방문 시간 정보를 통해서 K번 앞으로 달려나가는 것을 최적화 시킨다.
전체코드
from collections import deque
import sys
input = sys.stdin.readline
inside = lambda x,y: 0<=x<W and 0<=y<H
dire = [(1,0),(0,1),(-1,0),(0,-1)]
H,W,K = map(int,input().split())
arr = [list(input()) for _ in range(H)]
sy,sx,ey,ex = map(lambda x: int(x)-1,input().split())
V = [[-1]*W for _ in range(H)]
V[sy][sx] = 0
Q = deque([(sx,sy)])
while Q:
x,y = Q.popleft()
for dx,dy in dire:
for step in range(1,K+1):
nx,ny = x+step*dx, y+step*dy
if inside(nx,ny) and arr[ny][nx] == '.':
# 방문처리가 된 노드에 방문하는 경우
if V[ny][nx] != -1:
# 만약 현재 노드가 늦게 도착한 경우 현재 방향은 볼 필요가 없다
if V[y][x] >= V[ny][nx]:
break
# 현재 도착한 노드가 더 빠른 경우 그 다음 step을 늘리면서 넘어간다.
continue # 교차로에서 V[ny][nx]를 기록한 방향과 다를경우 그 다른 방향으로 탐색할 여지를 남겨줘야함
V[ny][nx] = V[y][x] + 1
Q.append((nx,ny))
else:
break
print(V[ey][ex])
코멘트
생긴거만 보면 쉬워보였는데, 조건문을 깐깐하게 걸어주지 않으면 TLE나는 문제
기존 경로 비교
V[ny][nx]는 이미 다른 경로로 해당 칸 (nx, ny)에 도달한 시간이 기록된 상태
현재 탐색 중인 경로가 해당 칸에 도달하는 시간이 같거나 느리면 (V[y][x] >= V[ny][nx]), 더 좋은 결과를 낼 가능성이 없음
효율적 탐색
continue는 현재 진입하는 방향을 전부 탐색하지 않았는데도 불구하고, 다른 방향에서 기록된 V로 인해서 경로가 막히는 것을 방지함
댓글