[Python] boj no. 2412 : 암벽 등반

Problem

https://www.acmicpc.net/problem/2412

Idea

각 홈을 정점으로 두고 (0, 0)을 시작 정점으로 하여 bfs를 하여 y 좌표가 T일 때의 이동 횟수를 구하였다.

처음에 2차원 리스트를 통해 홈의 좌표의 관리를 하려고 했으나 x 좌표는 최대 1,000,000, y 좌표는 최대 200,000 이므로 리스트의 크기가 너무 커진다는 문제가 있었다. 이를 해결하기 위해, 각 홈의 좌표는 고유한 한 쌍의 수 이므로 set을 통해 좌표를 관리하였다.

각 정점을 탐색할 때마다 이동 거리 범위 안에 홈이 있는다면 이동하며 홈 좌표에서 삭제하여 중복으로 탐색하는 일을 방지하였다.

Code

import sys
from collections import deque

input = sys.stdin.readline

n, T = map(int, input().split())
node = set()
for _ in range(n):
    x, y = map(int, input().split())
    node.add((x, y))
    
queue = deque()
queue.append((0, 0, 0))
while queue:
    cnt, cx, cy = queue.popleft()
    if cy == T:
        print(cnt)
        break
    
    for i in range(-2, 3):
        for j in range(-2, 3):
            if (cx+i, cy+j) in node:
                queue.append((cnt+1, cx+i, cy+j))
                node.remove((cx+i, cy+j))
else:
    print(-1)

Comment