백준 7562: 나이트의 이동 - BFS(파이썬)

나이트의 이동 성공다국어

7562번: 나이트의 이동

문제

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

입력

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

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

출력

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

 

내 코드

import sys
from collections import deque

def bfs(start_x, start_y):
    visited[start_x][start_y]=1 #시작점 방문 처리

    #덱 생성 + 시작점 append.
    que=deque() 
    que.append([start_x,start_y])

    while que:
        x,y=que.popleft()

        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=n: #좌표 범위 밖이면 불가능.
                continue

            if visited[nx][ny]==0: #이 점이 아직 방문X 이면,
                visited[nx][ny]=visited[x][y]+1 #이동 전의 좌표가 가진 값+1로 값 세팅.
                if nx==c and ny==d: #이동 후 좌표가 우리의 목적지이면,
                    return #함수를 종료.
                que.append([nx,ny])


#메인 코드 부분
t=int(sys.stdin.readline())

#나이트의 이동 가능 좌표(변화율)
dx=[-2,-2,-1,-1,1,1,2,2]
dy=[-1,1,-2,2,-2,2,-1,1]

for _ in range(t):
    n=int(sys.stdin.readline())
    a,b=map(int,sys.stdin.readline().split()) #출발좌표 (a,b)
    c,d=map(int,sys.stdin.readline().split()) #도착좌표 (c,d)

    visited=[]
    for _ in range(n):
        visited.append([0]*n)

    bfs(a,b)

    print(visited[c][d]-1) #시작점을 1로 해서 1을 뺴줘야 원하는 답이 됨

 

풀이 및 접근)

- 일반적인 BFS 문제와 다를 것이 없는 문제이다. 기존에 상하좌우 인접에 대한 문제가 많았다면, 이 문제는 상하좌우가 아니라 나이트의 이동 경우의 수를 생각하면 다른 점이 없다.

- 미로의 최단거리 문제와 같이 BFS를 하면서 좌표가 가진 값들을 이전의 값+1로 업데이트 하면서 이동하는데의 최소값을 구하는 것이다.

- 값을 세팅하는 부분에서 그 좌표가 목적지 좌표와 같다면 함수를 종료한다. 이 코드가 없어도 결국 답을 찾는데는 지장이 없지만 시간을 줄일 수 있다.

- 코드의 주석을 보면 이해가 잘 될 것이다.