BOJ 7562 - 나이트의 이동

문제

백준 온라인 저지 - 7562번

풀이 과정

나이트가 이동할 수 있는 방향을 통해 목표 지점에 도달하는 최소 이동 횟수를 찾아주는 문제입니다.
이동할 수 있는 방향이 8가지라는 점을 제외하면 일반적인 BFS 탐색 풀이법으로 해결할 수 있습니다.

코드

import sys
from collections import deque


T = int(input())
test_case = []
for _ in range(T):
    L = int(input())
    cur = list(map(int, sys.stdin.readline().split()))
    goal = list(map(int, sys.stdin.readline().split()))
    test_case.append([L, cur, goal])


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


def bfs(L, start, goal):

    q = deque()
    visit = [[False] * L for _ in range(L)]

    visit[start[0]][start[1]] = True
    q.append((start[0], start[1], 0))

    while q:
        x, y, cost = q.popleft()
        if x == goal[0] and y == goal[1]:
            return cost

        for i in range(8):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < L and 0 <= next_y < L and not visit[next_x][next_y]:
                visit[next_x][next_y] = True
                q.append((next_x, next_y, cost + 1))


def solution():
    for case in test_case:
        print(bfs(case[0], case[1], case[2]))


solution()