[백준] 암벽 등반 2412번 (Python)

문제

어떤 암벽에 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

---

풀이방법

• list의 시간 복잡도
  • append = O(1)
  • remove = O(n)
• set의 시간 복잡도
  • add = O(1)
  • remove = O(1)

리스트를 사용할 때의 시간초과를 set을 사용하여 해결

• 홈이 파여있는곳들을 다 기록한다.
• bfs로 탐색한다.
• -2 ~ 2까지의 범위내에 홈이 있다면 큐에 넣고 한번 사용된 홈은 제거한다.
• 높이 y 가 T와 같아진다면 종료

import sys
from collections import deque
# n : 암벽에 파인 홈의 개수, T : 도달할 높이
n, T = map(int, sys.stdin.readline().rstrip().split())

dot = set()
for i in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    dot.add((x,y))

queue = deque()
queue.append([0, 0, 0])
flag = False
while queue:
    x, y, count = queue.popleft()
    if y == T:
        flag =True
        break
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx = x + i
            ny = y + j
            if (nx, ny) in dot:
                queue.append([nx, ny, count + 1])
                dot.remove((nx, ny))
                
if flag:
    print(count)
else:
    print(-1)