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

문제 보러 가기 : 7562번: 나이트의 이동

시간제한: 1초
메모리제한: 256 MB

문제

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

입력

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

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

출력

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

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

---

또 다시 새로운 문제를 구글링 없이 스스로 풀었다. 뿌듯하다

import sys
from collections import deque 

sys.stdin=open('input.txt', 'r')

dx=[-2,-2,-1,-1,1,1,2,2]    # 말의 가능한 움직임 세트 
dy=[-1,1,-2,2,2,-2,-1,1]

if __name__=="__main__":
    T=int(input())            # 테스트셋

    for _ in range(T):
        I=int(input())
        CP=list(map(int, input().split()))
        TP=list(map(int, input().split()))
        board=[[0]*I for _ in range(I)]        # 체스보드를 0으로 채우고 
        board[CP[0]][CP[1]]=1                # 몇번째에 움직였는지 기록한다
        Q=deque()
        Q.append(CP)

        while Q:
            x,y=Q.popleft()
            for i in range(8):
                nx=x+dx[i]
                ny=y+dy[i]
                if 0<=nx<I and 0<=ny<I and board[nx][ny]==0:    # 한번도 방문한 적 없는 곳이면 
                    board[nx][ny]=board[x][y]+1                    # 이전 움직임 + 1을 해준다.
                    Q.append((nx,ny))

        print(board[TP[0]][TP[1]]-1)                            # 시작을 1로 표기했으니 마지막 답은 1을 빼준다

BFS도 하다보니 뻔한 문제였다.