[BOJ 2412 🥇4] 암벽 등반 (Python)

https://www.acmicpc.net/problem/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을 출력한다.

예제 입력 1 

5 3
1 2
6 3
4 1
3 2
0 2

 

예제 출력 1 

4

 

⭕ CODE

from collections import deque

n, t = map(int, input().split())

arr = set()

for _ in range(n):
    x, y = map(int, input().split())

    arr.add((x, y))

q = deque()
q.append((0, 0, 0))

# 정상에 오를 수 있는지 없는지 체크하기 위한 flag
flag = False

while q:
    # x좌표 y좌표 이동 회수
    x, y, count = q.popleft()

    # 만약 높이가 t라면 정상이므로 flag는 True로 변환후 멈춤
    if y == t:
        flag = True
        break

    # |a - x| ≤ 2이고 |b - y| ≤ 2 이므로 
    # -2 부터 2 까지 이동 가능하므로 범위 지정
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x + i
            ny = y + j

            # 다음 위치가 arr 즉 이동 가능한 위치에 있다면
            # in을 사용하기 위해 위에서 arr을 set으로 지정
            if (nx, ny) in arr:
                # q에 담아주고
                # arr에서 삭제
                q.append((nx, ny, count + 1))
                arr.remove((nx, ny))

# 정상에 오를 수 있다면 이동 회수 출력 
if flag:
    print(count)
# 아니라면 -1 출력
else:
    print(-1)

✏️ Comment

출발 지점에서 bfs를 사용하여 문제를 해결
나중에 in을 이용하여 다음 위치를 찾기 위해서 arr을 set으로 사용하여 시간을 단축시켰다.