Sign in Subscribe
PS

[PS] BOJ 7562 / 나이트의 이동

Minjun Kim

• 2 min read
[PS] BOJ 7562 / 나이트의 이동
Thumbnail: Photo by Hassan Pasha (Unsplash)
문제 링크: https://www.acmicpc.net/problem/7562

격자 그래프 상에서의 그래프 탐색 문제입니다.

풀이

​격자 그래프 상의 그래프 탐색

이제는 익숙한 문제 유형입니다. DFS 또는 BFS를 사용해, 2차원 배열 내의 각 좌표의 방문 여부를 기록하며 목적지를 찾아가면 됩니다. 다만, 상하좌우로의 단순한 이동이 아닌 나이트의 이동이므로 다음 좌표를 적절히 계산해주면 됩니다.

저는 우선순위 큐 기반의 BFS로 구현했습니다.

전체 코드

from heapq import heappush, heappop
input = open(0).readline
board = [[False] * 300 for _ in range(300)] # 체스 보드판. 방문 여부를 기록한다.
queue = [] # 우선순위 큐
KNIGHT_MOVES = (
    (-2, -1), (-1, -2), 
    (1, -2), (2, -1), 
    (-2, 1), (-1, 2),
    (1, 2), (2, 1)
) # 나이트가 이동 가능한 다음 좌표를 저장한 배열

def init_board(n):
    queue.clear()
    for r in range(n):
        for c in range(n):
            board[r][c] = False

def move_knight(n, start, end):
    init_board(n)
    heappush(queue, (0, *start))
    while queue:
        cnt, r, c = heappop(queue)

        for dr, dc in KNIGHT_MOVES:
            nr = r + dr
            nc = c + dc
            if 0 <= nr < n and 0 <= nc < n and not board[nr][nc]:
                board[nr][nc] = True
                if nr == end[0] and nc == end[1]:
                    return cnt + 1
                heappush(queue, (cnt + 1, nr, nc))

for _ in range(int(input())):
    N = int(input())
    start = tuple(map(int, input().split()))
    end = tuple(map(int, input().split()))
    if start[0] == end[0] and start[1] == end[1]:
        print(0)
    else:
        res = move_knight(N, start, end)
        print(res)

solution.py