파이썬 | 백준 | 7562 | 나이트의 이동 | BFS

solution

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

2. deque 이용

# 7562, 나이트의 이동
import sys
from collections import deque

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

def bfs(x, y):
    q.append((x, y))
    visited[x][y] = 1
    
    while q:
        x3, y3 = q.popleft()
        
        if x3 == x2 and y3 == y2:
            return visited[x3][y3]-1
            
        for i in range(8):
            nx = x3 + dx[i]
            ny = y3 + dy[i]

            if 0 <= nx < l and 0 <= ny < l:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x3][y3] + 1
                    q.append((nx, ny))

# 테스트 케이스 개수
T = int(sys.stdin.readline())
for _ in range(T):
    l = int(sys.stdin.readline())   # 체스판 한 변의 길이
    visited = [[0]*l for _ in range(l)]
    x1, y1 = map(int, sys.stdin.readline().split())     # 출발 위치
    x2, y2 = map(int, sys.stdin.readline().split())     # 도착 위치

    q = deque()
    print(bfs(x1, y1))

32920KB

2848ms

 

문제 출처 https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동