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

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

7562번: 나이트의 이동

나이트의 이동 성공

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

38533

19291

14421

49.061%

문제

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

입력

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

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

출력

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

 

<문제풀이>

from collections import deque

t = int(input())  # 테스트 케이스
dx = [-2, -2, 2, 2, 1, 1, -1, -1]
dy = [-1, 1, -1, 1, 2, -2, 2, -2]  # 8가지 방향 정의


def bfs():  # bfs 함수정의

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx >= l or ny >= l or nx < 0 or ny < 0:
                continue

            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))


for _ in range(t):  # 테스트 케이스 만큼 반복
    queue = deque()
    l = int(input())
    graph = [[0] * l for i in range(l)]  # l*l 리스트 생성
    a, b = map(int, input().split())  # 시작 지점
    c, d = map(int, input().split())  # 목적지
    if (a, b) == (c, d): # 출발지점과 목적지가 같다면 0 출력
        print(0)
        continue
    queue.append((a, b)) # queue에 시작지점 저장
    bfs() # bfs 실행
    print(graph[c][d]) # 정답출력