백준 BOJ 6146 : 신아를 만나러 - 파이썬

문제

키파는 신아를 만나러 아침 일찍(무려 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