백준: 7526 나이트의 이동

문제

7562번: 나이트의 이동

 

문제 풀이

  앞서 다룬 2178 미로 탐색과 동일한 방식으로 풀면 된다. 차이점이 있다면 탐색하는 방향이 대각선 8 방향이라는 것뿐이다. 나이트가 이동할 수 있는 경로로 이동할 때, 현재 경로까지 오는데 이동한 횟수를 계속 누적해가며 이동하면 된다. 따라서 원하는 도착 위치에 도착했을 때 중첩된 값이 찾고자 하는 답이다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < l and 0 <= y < l and not graph[x][y]


def bfs(start, end):
    q = deque([start])

    while q:
        if q[0] == end:
            x, y = end
            break

        cur_x, cur_y = q.popleft()

        for x, y in dirs:
            next_x, next_y = x + cur_x, y + cur_y
            if visitable(next_x, next_y):
                graph[next_x][next_y] = graph[cur_x][cur_y] + 1
                q.append([next_x, next_y])

    return graph[x][y]


if __name__ == "__main__":
    tc = int(stdin.readline())

    for _ in range(tc):
        l = int(stdin.readline())
        start = list(map(int, stdin.readline().split()))
        end = list(map(int, stdin.readline().split()))
        dirs = ((-1, 2), (1, 2), (2, 1), (2, - 1),
                (1, -2), (-1, -2), (-2, -1), (-2, 1))

        graph = [[0] * l for _ in range(l)]
        print(bfs(start, end))