[DFS&BFS / 중급] 7562 나이트의 이동 (백준, Python, 실버1)

문제 출처 : https://www.acmicpc.net/problem/7562

문제

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

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

출력

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

예제 입력 1

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

예제 출력 1

5
28
0

풀이

1-1. 이미 출발지 = 목표지 이면 0을 print 해준다.

1-2. q에 시작점을 넣어준다.

2. while q:
   1. q에서 나올때마다 트리가 깊어지는 것이므로 갈 때마다 1 더한다 => maps에 기록한다.
   2. 나이트가 갈수 있는 경로를 for문으로 돌리고, 방문되지 않은 점(maps에 깊이를 저장하기 때문에 0인 지점이 방문되지 않은 점이다.)이거나 maps를 벗어나지 않는지 확인한다.
   3. target에 오면 멈춘다.

문제풀이

• BFS

from collections import deque
import sys
input = sys.stdin.readline
test_case = int(input())

movin = [[1, 2], [-1, -2], [-1, 2], [1, -2], [2, 1], [-2, -1], [-2, 1], [2, -1]]

for t in range(test_case):
    q = deque()

    i = int(input())
    maps = [[0 for _ in range(i)] for i_ in range(i)]
    ii, jj = map(int, input().split())  # 출발지
    iii, jjj = map(int, input().split())    # 목표지

    if (ii == iii and jj == jjj):
        print(0)
        continue

    q.append([ii, jj])

    ans = 0

    while q:
        q_item = q.popleft()
        qx, qy = q_item[0], q_item[1]
        maps[qx][qy] += 1

        for mov in movin:
            x, y = mov[0], mov[1]

            if 0 <= qx + x < i and 0 <= qy + y < i and not maps[qx+x][qy+y]:
                maps[qx+x][qy+y] = maps[qx][qy]
                q.append([qx + x, qy + y])

            if x + qx == iii and y + qy == jjj: # 목표지에 도착했으면
                ans = maps[qx+x][qy+y]
                break
        if ans:
            print(ans)
            break