[백준/Python] BOJ 7562 - 나이트의 이동

👀 문제

7562번: 나이트의 이동 ✨ 실버 1

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

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

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

🔑 키포인트

그래프 이론 BFS (너비 우선 탐색)

⛑️ 실수했던 점

👉 현재 위치와 이동하려는 곳의 위치가 같은 경우

현재 나이트의 위치와 가려고 하는 곳의 위치가 같은 경우 0을 출력해 주는 코드를 추가해 주었다.

✍️ 코드

import sys
from collections import deque
input = sys.stdin.readline

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        # 나이트가 이동할 수 있는 칸 탐색
        for i in range(8):
            nx = x + dx[i]
            ny  = y + dy[i]

            if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
                graph[nx][ny] = graph[x][y] + 1

T = int(input()) # 테스트케이스의 개수

for _ in range(T):
    I = int(input())

    graph = [[0]*I for _ in range(I)]
    visited = [[False]*I for _ in range(I)]

    nowX, nowY = map(int, input().split())
    goX, goY = map(int, input().split())

    if nowX == goX and nowY == goY: # 현재 위치와 이동하려는 위치가 같은 경우 0 출력
        print(0)
    else:
        bfs(nowX, nowY)
        print(graph[goX][goY])