[백준] 7562 in Python 파이썬 풀이

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

7562번: 나이트의 이동

 

steps 는 나이트가 이동할 수 있는 경우의 수를 배열로 표현했다. 

핵심은 나이트가 이동할 때마다 그래프 상에서 이번 이동하면 몇번째인지 기록해두는 것이다 바로바로 이렇게 ! 

graph[nx][ny] = graph[x][y] + 1

graph[x][y]에는 x,y 위치로 오기까지의 step 횟수가 저장되어 있을것이므로 이 값에 1을 더한것이 새로운 위치인 nx, ny 까지 이동하는데 걸린 횟수이다 ! 풀이 방법이 DP스럽기도 하다

내 풀이

from collections import deque
t = int(input())
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

for i in range(t):
    n = int(input())
    x, y = map(int, input().split()) # 현재 위치
    a, b = map(int, input().split())
    graph = [[0]*n for _ in range(n)]
    q = deque()
    q.append([x, y])

    while q:
        x, y = q.popleft()
        if x == a and y == b:
            break

        for step in steps:
            nx = x + step[0]
            ny = y + step[1]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                q.append([nx, ny])
    print(graph[a][b])