[BFS] 백준 #7562 나이트의 이동 - Python

🗂️ 문제

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

 

💡 접근법

나이트가 이동할 수 있는 범위를 dx와 dy로 생성한다.

이후 맵의 크기에 맞게 False로 maps를 초기화하고, deque를 통해 큐를 생성한다.

 

초기 시작 위치값인 a와 b를 입력받고, maps[a][b]=0으로 초기화한다.

while()문을 통해 큐의 맨 왼쪽 값을 pop하면서 나이트가 이동할 수 있는 범위를 모두 탐색한다. 이때 맵을 벗어나지 않으면서 방문한 적 없는 위치일 경우 큐에 현재 위치를 추가하고 maps에 현재 값을 업데이트한다. 이때 업데이트되는 값은 처음부터 지금까지 이동한 횟수를 나타낸다.

 

만약 종료 위치에 도달했을 경우 큐를 비워 while문을 빠져나온다.

최종적으로 이동하려는 위치에 해당하는 maps의 값을 출력한다.

 

😎 내 코드

import sys
from collections import deque

T = int(sys.stdin.readline())

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

for _ in range(T):
    I = int(sys.stdin.readline())
    a, b = map(int, sys.stdin.readline().split())
    rx, ry = map(int, sys.stdin.readline().split())

    maps = [[False] * I for _ in range(I)]
    maps[a][b] = 0
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx == a and ny == b:
                continue
            if -1 < nx < I and -1 < ny < I:
                if not maps[nx][ny]:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))
            
            if rx == nx and ry == ny:  # 종료조건
                queue = []
                break
 
    print(maps[rx][ry])

 

✅ 정답 확인