Baekjoon 7562 | 나이트의 이동 (Python)

📌문제

SILVER1 / 너비 우선 탐색 / 그래프 이론 / 그래프 탐색

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

 

[문제 설명]

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[입력]

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

[출력]

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

[예제]

📌문제 분석 및 설계

코딩 테스트 연습을 좀 쉬워서 만만한 bfs문제부터 풀었다..!

이 문제의 핵심은 "최단거리 추적" 이라고 생각했다.

 

따라서 visited 행렬을 최단거리 추적하는 겸 용으로 사용했다!

 

 

📌소스 코드

from collections import deque
dxs,dys=[1,2,2,1,-1,-2,-2,-1],[-2,-1,1,2,-2,-1,1,2]

def in_range(x,y):
    return 0<=x<l and 0<=y<l

def bfs(l,startx,starty,endx,endy):
    visited=[[0]*l for _ in range(l)]
    dq=deque([(startx,starty)])
    visited[startx][starty]=1
    while dq:
        x,y=dq.popleft()
        if (x,y)==(endx,endy):
            return visited[x][y]-1
        for dx,dy in zip(dxs,dys):
            nx,ny=x+dx,y+dy
            if in_range(nx,ny) and visited[nx][ny]==0:
                dq.append((nx,ny))
                visited[nx][ny]=visited[x][y]+1 #최단거리 추적

n_test=int(input())
for test in range(n_test):
    l=int(input())
    startx,starty=map(int,input().split())
    endx,endy=map(int,input().split())
    print(bfs(l,startx,starty,endx,endy))