[백준/Python] 7562번 : 나이트의 이동

문제 정보

제목 : 나이트의 이동

번호 : 7562번

사용 언어 : Python

문제 링크

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

7562번: 나이트의 이동

 

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

 

문제

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

 

입력

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

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

 

출력

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

 

입출력 예제

---

나의 풀이

BFS 함수를 목적지에 도착하는 최소 이동 수를 return하도록 정의했습니다. 매개변수로 체스판의 한 변의 길이 l, 현재 위치 sP, 목적지 eP를 받아와서 체스판을 2차원 배열 형태로 정의하고, 나이트가 이동할 수 있는 방향인 8개를 direct 리스트에 저장합니다. deque를 선언하여 현재 위치를 queue에 저장하고 chessBoard는 방문 했다는 의미인 1을 저장합니다.

queue에 요소가 있는 동안 반복하는 while 루프를 이용합니다. queue.popleft()을 통해 현재 나이트의 위치를 각각 변수에 저장하고, 현재 위치가 목적지와 같다면 chessBoard의 현재 위치의 값 -1을 return합니다. 목적지가 아니라면 갈 수 있는 방향을 순회하며, 다음 이동할 위치를 구합니다. 다음 이동할 위치가 체스판의 범위 안이고, 방문을 안했다면 다음 이동 위치 방문 여부 리스트에 현재 위치의 이동 횟수 +1을 저장하고, 다음 이동할 위치를 queue에 저장합니다.

테스트 케이스 횟수만큼 반복하는 for 루프를 이용해, 입력값들을 받아 BFS를 수행하고 return값을 answer에 저장하여 출력합니다.

 

코드

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

# BFS 함수 정의
def BFS(l,sP,eP):
    chessBoard = [[0 for _ in range(l)] for _ in range(l)]
    direct = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] # 나이트가 갈 수 있는 방향 저장
    queue = deque([sP])
    chessBoard[sP[0]][sP[1]] = 1

    while(queue) :
        curY,curX = queue.popleft()

        if( curY == eP[0] and curX == eP[1]) :
            return chessBoard[curY][curX] - 1

        for dy,dx in direct :
             nextY = curY + dy
             nextX = curX + dx
             if( 0<= nextY < l and 0<= nextX < l):
                 if(chessBoard[nextY][nextX] == 0 ) :
                     chessBoard[nextY][nextX] = chessBoard[curY][curX] + 1
                     queue.append([nextY,nextX])
    return 0

# 테스트 케이스 개수 입력
T = int(input())

# 테스트케이스별로 입력받아서 BFS 수행
for i in range(T):
    l = int(input()) # 체스판의 한 변의 길이
    start = list(map(int,input().split())) # 나이트의 현재 위치
    end = list(map(int,input().split())) # 나이트가 이동하려고 하는 위치
    answer = BFS(l, start, end)
    print(answer)