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

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

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

7562번: 나이트의 이동

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

---

생각한 과정

전형적인 BFS 문제였다.

좀 다른 점은 지금까지 푼 BFS 문제는 상하좌우만 이동했지만, 이 문제는 체스할 때 나이트가 갈 수 있는 방향으로 이동해야한다. (한 칸 직진, 대각선)

 

그래서 BFS 문제 풀 때, 만든 nx, ny 리스트 조금만 바꾸면 쉽게 풀린다!!!!

 

---

코드

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

T = int(input()) # 테스트 수
# 나이트가 갈 수 있는 경우의 수 8가지
dx = [-2,-2, 2, 2, -1, -1, 1, 1]
dy = [-1, 1,-1, 1, -2, 2, -2, 2]

for _ in range(T):
    status = 0 # 원하는 위치에 도달했는지 확인할 변수
    I = int(input()) # 체스판 크기 n x n
    curX, curY = map(int, input().split()) # 현재 나이트 위치
    wantX, wantY = map(int, input().split()) # 원하는 위치

    # 방문처리 할 체스판 0으로 초기화
    graph = [[0]*I for _ in range(I)]

    queue = deque()
    queue.append((curX, curY)) # 처음 위치 큐에 넣기
    
    while queue:
        x, y = queue.popleft()
        if x == wantX and y == wantY: # 처음 위치랑 원하는 위치가 같으면 break
            break
            
        for i in range(8): # 8가지 경우의 수 돌기
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < I and 0 <= ny < I: # 범위 내에 있으면
                if nx == wantX and ny == wantY: # 도달했으면
                    graph[nx][ny] = graph[x][y] + 1 # 횟수 + 1
                    status = 1 # 원하는 위치에 도달했으므로 1로 체크
                    break

                if nx == curX and ny == curY: # 처음 위치와 같으면
                    continue

                if graph[nx][ny] != 0: # 이미 방문했으면
                    continue
                
                queue.append((nx, ny)) # 큐에 넣기
                graph[nx][ny] = graph[x][y] + 1
        
        if status == 1:
            break
    
    print(graph[wantX][wantY])