[Python/파이썬] 백준 2412번 암벽 등반

2412번: 암벽 등반

 

문제

어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.

현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.

입력

첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.

출력

첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.

코드

import sys
input = sys.stdin.readline
from collections import deque, defaultdict
 
n, t = map(int, input().split())
wall = defaultdict(list)
for _ in range(n):
    x, y = map(int, input().split())
    wall[y].append(x)

q = deque([(0, 0, 0)])

while q:
    x, y, cnt = q.popleft()
    if y == t:  # 정상에 오르기 성공
        print(cnt)
        exit()
    for b in range(-2, 3):
        if y+b in wall:
            remove_lst = []
            for a in wall[y+b]:
                if abs(a-x) <= 2:
                    q.append((a,y+b,cnt+1))
                    remove_lst.append(a)
            # 이용한 홈 리스트에서 제거 -> 방문처리
            for r in remove_lst:
                wall[y+b].remove(r)
print(-1)

 

BFS를 응용하여 풀이하였다.

입력받은 홈들의 정보를 y 좌표를 키, x 좌표들 리스트를 값으로 갖는 defaultdict(wall)에 저장해준다.

그리고 deque에 처음 위치와 이동횟수를 담은 튜플 (0, 0, 0)을 넣어주고 BFS를 돌린다.

y 좌표가 위아래로 -2 ~ 2인 홈들에 대해 살펴보며 이동할 수 있는 홈의 경우 큐에 추가하고 리스트에서 지워준다.

y 좌표가 T와 같은 값이 나온다면 정상에 도달한 것이므로 cnt 값을 출력하고 프로그램을 종료한다. 만약 중간에 종료되지 못하고 q가 비어서 while문이 끝나게 된다면 정상에 오를 수 없는 경우이므로 -1을 출력해준다.