[BOJ] 6146: 신아를 만나러(Python)

6146번: 신아를 만나러

문제 설명

키파가 웅덩이를 피해 신아에게 갈 수 있는 최소 거리를 구해보자.

나의 풀이

import sys
from collections import deque
input=sys.stdin.readline

X,Y,n=map(int,input().split())
X+=500
Y+=500
graph=[[0]*(1001) for _ in range(1001)]
graph[500][500]=1
d=[(0,1),(0,-1),(1,0),(-1,0)]

for _ in range(n):
    a,b=map(int,input().split())
    graph[a+500][b+500]=2

def func():
    q=deque()
    q.append([500,500])
    while q:
        x,y=q.popleft()
        for dx,dy in d:
            nx,ny=dx+x,dy+y
            if nx==X and ny==Y:
                return graph[x][y]
            if 0<=nx<=1000 and 0<=ny<=1000 and not graph[nx][ny]:
                graph[nx][ny]=graph[x][y]+1
                q.append([nx,ny])
                
print(func())

좌표가 -500~500 범위이므로 각 좌표에 500을 더해서 0~1000 범위로 변경한다. 이후에는 BFS를 사용해서 최소 경로를 찾아가면 된다.

시간복잡도

신아가 있는 공간을 탐색할 때 최대 O(1000^2)가 걸린다.