[백준 7562번] 나이트의 이동 python

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

 

 

 

- 문제 유형 : 그래프 탐색

- 소요 시간 : 약 3시간 -> 앞으로 줄여야 함.

- 어려웠던 부분 : 이동 횟수를 구할 때 어떤 방식을 사용해야 하는지 감을 못 잡음.

나이트가 첫번째 칸에서 두번째 칸으로 이동할 때 1증가, 두번째 칸에서 세번째 칸으로 이동할 때 1증가시키는 방식으로

마지막 최종 칸에 써지는 숫자가 최소 이동 횟수가 됨. (여기서 이미 숫자가 채워진 그래프 칸은 이동 횟수를 변경시키지 않기 위해 graph[nx][ny]== 0인지 따져보는 것)

 

[구현 코드]

from collections import deque

def bfs(x, y):

    q = deque()

    q.append((x, y))

   

    while q :

       

        x, y = q.popleft()

       

        if x == x2 and y == y2 :

            return graph[x2][y2]

       

        for k in range(8):

            nx = x + dx[k]

            ny = y + dy[k]

            if 0 <= nx < I and 0 <= ny < I and graph[nx][ny] == 0:

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

                q.append((nx,ny))

                # print(q)

 

test_case = int(input())

for i in range(1, test_case + 1) :

    I = int(input())

    x1, y1 = map(int, input().split())

    x2, y2 = map(int, input().split())

   

    graph = [[0] * I for _ in range(I)]

    graph[x1][y1] = 0

   

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

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

   

    print(bfs(x1, y1))