파이썬으로 주어진 경유지를 거쳐 목적지에 도달할 수 있는지 판별하는 프로그램

문제 설명

2차원 공간에 포인터가 좌표 (px, py)를 갖는 점 p에 위치해 있다고 가정해 봅시다. 이 포인터는 좌표 (qx, qy)를 갖는 점 q로 이동해야 하지만, 자유롭게 움직일 수는 없습니다. 포인터는 현재 위치를 기준으로 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 네 방향에 있는 점으로만 한 칸씩 이동할 수 있습니다.

여러 좌표 점을 담고 있는 배열 'paths'가 주어집니다. 이 배열의 점들은 반드시 순서대로 처리해야 하며, 해당 점으로 실제 이동이 불가능한 경우에도 배열의 모든 점은 처리 대상에 포함됩니다.

따라서 시작점과 목적지가 주어졌을 때, 포인터가 주어진 점들을 거쳐 목적지에 도달할 수 있는지 판별해야 합니다. 도달이 가능하면 목적지까지 이동하며 거친 총 점의 개수를 출력하고, 불가능하다면 -1을 출력합니다.

예시

입력이 px = 1, py = 1, qx = 2, qy = 3, paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]이라면 출력은 4가 됩니다.

점들을 순서대로 처리하면 다음과 같습니다.

점 (1, 2): 이동 성공 → 현재 포인터 위치 (1, 2), 거친 점의 수: 1
점 (0, 1): 이동 실패 → 현재 포인터 위치 (1, 2), 거친 점의 수: 2
점 (0, 2): 이동 실패 → 현재 포인터 위치 (1, 2), 거친 점의 수: 3
점 (1, 3): 이동 성공 → 현재 포인터 위치 (1, 3), 거친 점의 수: 4

목적지 (2, 3)는 현재 포인터 위치 (1, 3)에서 (x+1, y) 방향에 있으므로, 거친 총 점의 개수는 4입니다.

해결 접근 방법

이 문제는 BFS(너비 우선 탐색)와 이진 탐색을 조합하면 효율적으로 해결할 수 있습니다. 다음 단계를 따릅니다.

helper() 함수를 정의합니다. 이 함수는 정수 k를 받아 paths의 앞에서 k개의 점만 사용했을 때 목적지 도달 가능 여부를 반환합니다.
- vertices := (px, py)와 (qx, qy)를 포함하는 새로운 집합을 만듭니다.
- paths의 첫 번째부터 k번째까지의 각 (x, y)를 vertices에 추가합니다.
- trav := (px, py)를 담은 새로운 deque를 생성합니다.
- trav가 빌 때까지 다음을 반복합니다.
  - (x, y) := trav의 가장 앞 항목을 꺼냅니다.
  - (x, y)가 (qx, qy)와 같으면 True를 반환합니다.
  - 네 방향 인접 좌표 (x-1, y), (x+1, y), (x, y-1), (x, y+1)의 각 (kx, ky)에 대해, 해당 좌표가 vertices에 존재하면 trav의 끝에 추가하고 vertices에서는 제거합니다(중복 방문 방지).
- 반복이 끝날 때까지 도달하지 못하면 False를 반환합니다.
ll := -1, ul := len(paths) + 1로 초기화한 뒤 이진 탐색을 수행하여, 목적지에 도달할 수 있는 최소한의 점 개수 k를 찾습니다.
탐색 종료 후 ul이 len(paths) 이하이면 ul을, 그렇지 않으면 -1을 반환합니다.

구현 예시

다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.

from collections import deque
def solve(px, py, qx, qy, paths):
    def helper(k):
        vertices = {(px, py), (qx, qy)}
        for x, y in paths[:k]:
            vertices.add((x, y))
        trav = deque([(px, py)])
        while trav:
            x, y = trav.popleft()
            if (x, y) == (qx, qy):
                return True
            for kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                if (kx, ky) in vertices:
                    trav.append((kx, ky))
                    vertices.remove((kx, ky))
        return False
    ll, ul = -1, len(paths) + 1
    while ll + 1 < ul:
        k = ll + (ul - ll) // 2
        if helper(k):
            ul = k
        else:
            ll = k
    return ul if ul <= len(paths) else -1

print(solve(1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]))

입력

1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]