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

7562 - 나이트의 이동

문제

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

코드

from collections import deque

def bfs(i, j, count):
    q = deque()
    q.append((i, j, count))

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

        if x == end_x and y == end_y:
            return cnt

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

            if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]:
                q.append((nx, ny, cnt + 1))
                visited[nx][ny] = True


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

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

    visited = [[False] * I for _ in range(I)]
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())

    result = bfs(start_x, start_y, 0)
    print(result)

한마디

나이트가 이동할 수 있는 8개의 방향을 설정하여 BFS로 풀었다.

7562번: 나이트의 이동