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

문제 설명

 

입출력 예제

 

---

풀이 코드

전형적인 bfs (너비 우선 탐색) 문제 이지만 딱 한가지 다른점이 있다.

바로 이동방향이다.

문제의 이동 방향을 보면 실제 체스의 나이트가 이동할 수 있는 것 처럼 대각선으로 2칸씩 8방향으로 움직인다.

나이트의 이동방향을 표현하면 다음과 같이 표현할 수 있다.

 

정답 코드

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

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

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

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

        if x == ex and y == ey:
            return chessmap[x][y]

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < l and 0 <= ny < l and chessmap[nx][ny] == 0:
                q.append((nx, ny))
                chessmap[nx][ny] = chessmap[x][y] + 1


for _ in range(int(input())): # 테스트 케이스
    l = int(input()) # 한 변의 길이
    chessmap = [[0] * l for _ in range(l)]
    sx, sy = map(int, input().split()) # 시작지점 행, 열
    ex, ey = map(int, input().split()) # 도착지점 행, 열
    print(bfs(sx, sy))