[파이썬, Python] 백준 7562: 나이트의 이동

문제

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

코드

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

t = int(input())

for i in range(t):
    l = int(input())

    start = list(map(int, input().split()))
    dest = list(map(int, input().split()))

    dis = [[-1 for _ in range(l)] for _ in range(l)]

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

    #bfs
    q = deque([(start[0], start[1])])
    dis[start[0]][start[1]] = 0

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

        if x == dest[0] and y == dest[1]:
            break

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

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

    print(dis[dest[0]][dest[1]])

설명

bfs를 통해 해결할 수 있었다.

우선 각 입력값을 받아주고 거리 정보를 세팅해 준다.

dx, dy를 세팅하는데 나이트의 이동 규칙에 맞게 8개의 길을 만들어준다.
나이트의 이동 경로는 문제에 나와있다.

deque을 이용해서 큐를 생성하여 bfs를 이용한다.

시작하면서 시작점의 좌표를 큐에 넣어주고 거리를 0으로 설정해 준다.
이때, 방문 처리도 같이 한다고 생각하면 된다.

q가 존재하는 동안 popleft를 해주어 해당 좌표에서 이동할 수 있는 칸을 계산하고
이동이 가능하다면 해당 칸의 거리를 현재 좌표의 dis + 1로 설정해 준다.

이를 반복하며 x와 y 좌표가 목표 좌표가 될 때까지 bfs를 돌린 후 break를 통해 탈출한다.

이후 좌표를 출력한다.