[백준] 7562 : 나이트의 이동 Python 문제풀이

나이트가 현재 있는 칸을 start_x, start_y에 저장
나이트가 이동하려는 칸을 end_x, end_y에 저장

방법 1

q에 나이트가 이동할 칸의 좌표와 몇 번째 이동인지 저장
q에 추가할 때마다 지도에 1로 업데이트
나이트가 이동하려는 칸에 도달하면 이동 횟수를 프린트하고 break.

정답코드

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

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

for _ in range(int(input())):
    l = int(input())
    m = [[0]*l for _ in range(l)]
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())
    ans = 0
    q = deque([(start_x, start_y, 0)])
    m[start_x][start_y] = 1
    while q:
        x, y, n = q.popleft()
        if x == end_x and y == end_y:
            print(n)
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx and nx < l and -1 < ny and ny < l and not m[nx][ny]:
                m[nx][ny] = 1
                q.append((nx,ny, n+1))

방법 2

q에 나이트가 이동할 칸의 좌표만 저장

m[nx][ny] = m[x][y] + 1

-> 나이트가 이동하려는 칸에 몇 번째 이동인지 업데이트.

정답코드

from collections import deque
import sys

input = sys.stdin.readline
dx = [-1,-2,-2,-1,+1,+2,+2,+1]
dy = [-2,-1,+1,+2,-2,-1,+1,+2]

for _ in range(int(input())):
    l = int(input())
    m = [[0]*l for _ in range(l)]
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())
    ans = 0
    q = deque([(start_x, start_y)])
    while q:
        x, y = q.popleft()
        if x == end_x and y == end_y:
            print(m[x][y])
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx and nx < l and -1 < ny and ny < l and not m[nx][ny]:
                m[nx][ny] = m[x][y] + 1
                q.append((nx,ny))