[Baekjoon] 7562번 : 나이트의 이동 (Python, 그래프, BFS)

[Baekjoon] 7562번 : 나이트의 이동 (Python, 그래프, BFS)

 

목차

 

 

 

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

7562번: 나이트의 이동

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 32468KB / 시간 2748ms / 코드 길이 805B

 

백트래킹 외 가장 쉬운 방법은 초기 진입한 최초 횟수를 기록하면서 진행하는 BFS이다.

고로 본 방법은 BFS로 문제를 푼다.

 

from collections import deque
dm = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

def bfs(current, target, cnt, visit):
    q = deque([current])
    visit[current[0]][current[1]] = 1

    while q:
        x, y = q.popleft()

        if [x,y] == target:
            return visit[x][y]

        for i in range(8):
            nx, ny = x+dm[i][0], y+dm[i][1]

            if nx < 0 or ny < 0 or nx >= l or ny >= l:
                continue
            if not visit[nx][ny]:
                visit[nx][ny] = visit[x][y] + 1
                q.append([nx, ny])

for _ in range(int(input())):
    l = int(input())
    present = list(map(int, input().split()))
    target = list(map(int, input().split()))

    visit = [[0]*l for _ in range(l)]
    val = bfs(present, target, 0, visit)
    print(val-1)