악곱 == 악성곱슬

BFS

---

해당 문제는 최단 경로를 구하는 문제이다. 다만 이동하는 주체가 나이트로 움직이는 방법이 정해져있다. 따라서 이동하는 방법을 move라는 배열로 저장하고 다음과 같이 구현할 수 있다.

그래프 유형의 문제를 구현할 때 최단 경로를 구하기 위해서는 그래프를 탐색해야 한다. 방법에는 DFS, BFS, Dijkstra, Floyd등을 떠올릴 수 있는데, 이 문제와 같이 격자무늬는 모두 간선의 비용이 1이므로, 간단하게 DFS, BFS로 간추릴 수 있다.

여기서 DFS로의 탐색은 그래프를 완전탐색 하지 않는이상 최단 경로를 구한다는 보장이 없기 때문에 BFS를 사용하여 구현하여 효율을 높인다. 코드는 다음과 같다.

import sys
from collections import deque

move = [
    (-1, -2), (-2, -1), (-2, 1), (-1, 2),
    (1, -2), (2, -1), (2, 1), (1, 2)
]

def bfs(start, target, length):
    q = deque()
    q.append(start)
    visited = [[False]*length for _ in range(length)]
    visited[start[0]][start[1]] = True
    while q:
        cur = q.popleft()
        # 원하는 위치 도착
        if cur[0] == target[0] and cur[1] == target[1]:
            return cur[2]
        # 8방향 탐색
        for x, y in move:
            nx = cur[0] + x
            ny = cur[1] + y
            # 인덱스 벗어남
            if nx < 0 or ny < 0 or nx >= length or ny >= length:
                continue
            # 방문했었음
            if visited[nx][ny] is True:
                continue
            # 이동
            q.append((nx, ny, cur[2] + 1))
            visited[nx][ny] = True

def solution(start, target, length):
    x, y = start
    return bfs((x, y, 0), target, length)

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        L = int(sys.stdin.readline().rstrip())
        graph = [[False] * L for _ in range(L)]
        S = list(map(int, sys.stdin.readline().rstrip().split()))
        T = list(map(int, sys.stdin.readline().rstrip().split()))
        print(solution(S, T, L))