[백준 알고리즘] 7562번 나이트의 이동, 파이썬(python)

7562, 나이트의 이동

📁 문제 출처

7562번: 나이트의 이동

 

💡 생각

• 나이트가 현재 위치에서 원하는 위치까지 최소 몇 번 이동해야지 도착할 수 있는지를 구하는 문제이다.
• 현재 위치에서 목적지까지 어떻게 가는가? -> [2178, 미로 탐색] 문제처럼 라벨링을 해주면서 진행

 

🛠 나의 코드

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

dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]


t = int(input())

for i in range(t):
    n = int(input())
    cx, cy = map(int, input().split()) 
    fx, fy = map(int, input().split())

    graph = [([0] * n) for i in range(n)]

    queue = deque()
    queue.append((cx, cy))
    graph[cx][cy] = 1

    while queue:
        x, y = queue.popleft()
        if x == fx and y == fy:
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    print(graph[fx][fy]-1)

 

✔️ 배운 점 및 주의할 점

• 이전에 이동 횟수를 기록하면서 나아가는 문제를 풀어보지 않았다면 이 아이디어를 떠올리기 어려웠을 것 같다.