[백준] 7562번: 나이트의 이동 - 파이썬

🧩문제 해석

체스 판의 크기와 현재 나이트의 위치 그리고 목표 위치가 주어졌을 때 최소 이동 횟수를 출력하는 프로그램!

 

📕 풀이

나이트의 이동 가능 경로는 다음과 아래의 그림과 같다. 
최소 이동 횟수를 구하려면 이전에 방문 했던 곳은 지양한다. 그리고 체스판에서 벗어나는 위치도 제외한다. 이 두가지를 지키면서 BFS 탐색을 하였다.
칸을 모두 방문하는 것이 아니라 목표 위치에 도달하면 탐색을 멈출 것이기에 DFS 보다 BFS가 더 효율적이다.

나이트의 이동 경로

💻 코드

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

# 나이트 이동 경로
dx = [-2,-1,1,2,2,1,-1,-2]
dy = [1,2,2,1,-1,-2,-2,-1]

def bfs():
    queue= deque()
    queue.append((x1, y1, 0)) # 현재 위치와 카운트 0을 큐에 삽입
    pan[x1][y1] = 1 # 방문 처리
    while queue: # 큐가 빌 때까지
        x,y,cnt = queue.popleft()
        for i in range(8): # 8가지 방향 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            if -1 < nx and nx < l and -1 < ny and ny < l: # 체스판에서 벗어나지 않는다면
                if pan[nx][ny] == 0: # 아직 방문하지 않았다면
                    pan[nx][ny] = 1 # 방문 처리
                    queue.append((nx, ny, cnt+1)) # 이동 위치와 카운트 +1을 큐에 삽입
            if nx == x2 and ny == y2: # 현재 위치가 목표 위치에 도달했다면 카운트 +1 리턴
                return cnt + 1
                
for i in range(int(input())):
    l = int(input().rstrip()) # 체스판 크기
    pan = [[0 for i in range(l)] for j in range(l)] # 방문 처리를 위한 리스트
    x1,y1 = map(int, input().rstrip().split()) # 현재 위치
    x2,y2 = map(int, input().rstrip().split()) # 목표 위치
    if x1 == x2 and y1 == y2: # 현재위치와 목표위치가 동일하다면 탐색하지 않고 바로 0출력
        print(0)
    else: # BFS 함수 호출
        print(bfs())

🔗 문제링크 : 나이트의 이동

7562번: 나이트의 이동