7562. 나이트의 이동

업데이트 시간 : 2023-06-13 09:00:59 +0000

[Silver I] 나이트의 이동 - 7562

문제 링크

성능 요약

메모리: 127148 KB, 시간: 336 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

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

입력

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

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

출력

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

💡 Solutions

📄 나이트의 이동.py

from collections import deque
T = int(input())

d = ((2,1),(1,2), (2,-1),(1,-2), (-2,1),(-1,2), (-2,-1),(-1,-2))

for _ in range(T):
    N = int(input())
    sx, sy = map(int,input().split())
    ex, ey = map(int,input().split())
    
    que = deque()
    matrix = [[False for _ in range(N)] for _ in range(N)]
    que.append((sx,sy, 0))
    matrix[sx][sy] = True
    ans = 0
    while que:
        x, y, depth = que.popleft()
        
        if x == ex and y == ey:
            ans = depth
            break
        
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= N or ny >= N : continue
            if matrix[nx][ny] : continue
            matrix[nx][ny] = True
            
            que.append((nx,ny, depth+1))
        
    print(ans)