[BOJ][⚪2][백준#07562] 나이트의 이동

문제 출처

BAEKJOON Online Judge #7562

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제

입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

출력

5
28
0

My Sol

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


def f(ni, nj):
    for di, dj in didj:
        if 0 <= ni + di < L and 0 <= nj + dj < L:
            if mat[ni+di][nj+dj] != -1:
                continue

            mat[ni+di][nj+dj] = mat[ni][nj]+1
            queue.append((ni+di, nj+dj))
    return


T = int(input())
for _ in range(T):
    L = int(input())
    mat = [[-1]*L for _ in range(L)]
    ni, nj = map(int, input().split())
    ti, tj = map(int, input().split())

    mat[ni][nj] = 0
    queue = [(ni, nj)]
    start = -1
    while mat[ti][tj] == -1:
        start += 1
        ni, nj = queue[start]
        f(ni, nj)
    print(mat[ti][tj])

queue를 사용하는 dfs문제였다. 현재 위치를 ni와 nj, 목표 위치를 ti와 tj로 하여 함수를 설정하였다. 벡터를 이용하였고, 경계 설정을 해주어 0과 l-1의 인덱스에서만 움직이도록 하였다. dp적 성질을 가지는 것은, 조회하는 위치가 초기값인 -1이 아니라면 queue에 넣지 않는 것이다. DP보다는 backtracking에 가깝겠다.

다만 이렇게 되면 사방팔방으로 ni, nj를 찍기 때문에 queue에도 불필요한 경로 좌표가 생기고, 그만큼 시간적인 낭비가 심할 것 같아 ti와 ni, di의 관계를 이용한 조건문을 하나 더 두었는데 테스트 케이스는 모두 맞춰도 백준의 나머지 테스트 케이스에 무결성 검사에서 걸려서 한참을 헤매다 조건을 빼니까 겨우 성공했다.

결과

맞았습니다!!