문제
키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다.
신아가 일찍 일어날 수도 있기 때문에 어서 (X, Y)에 있는 신아의 집에 최대한 빨리 도달해서 그녀가 잘 때 서프라이즈를 해 주고 싶지만, 장화가 새 것이기 때문에 웅덩이를 밟지 않는 것도 중요하다. 만일 키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가? 신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정한다.
입력
첫째 줄에 X, Y와 N이 공백을 사이에 두고 주어진다.
i+1 (1 ≤ i ≤ N) 번째 줄에 Ai와 Bi가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 키파가 웅덩이를 밟지 않고 신아에게 갈 수 있는 최소 거리를 출력하라.
예제 입력 1
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
예제 출력 1
11
제출 답안
from collections import deque
# 이동할 네가지 방향 정의 (상하좌우)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
X, Y, N = map(int, input().split())
graph = [[0]*1000 for _ in range(1000)]
for _ in range(N):
A, B = map(int, input().split())
graph[A][B] = -1
visited = [[False]*1000 for _ in range(1000)]
def bfs(x,y):
dq = deque([(x, y, 0)])
visited[x][y] = True
while dq:
x, y, cnt = dq.popleft()
if x == X and y == Y: # 신아의 위치에 도착하면
return cnt # 현재 칸 까지 이동한 횟수 리턴
for i in range(4): # 4가지 방향으로 위치확인
nx = x + dx[i]
ny = y + dy[i]
# 위치가 벗어나면 안되기 때문에 조건 추가 (물웅덩이는 -500~500 사이에 있을 수 있음)
if -500 <= nx < 500 and -500 <= ny < 500:
# 방문하지 않았고 -1(이동불가)이 아니라면
if not visited[nx][ny] and graph[nx][ny] != -1:
visited[nx][ny] = True
dq.append([nx, ny, cnt+1])
print(bfs(0,0)) # 키파의 시작 위치는 0,0