백준 7562 python 풀이 (나이트의 이동, BFS, 그래프)

문제는 나이트가 위와 같이 움직일 수 있을때 몇번 움직이면 원하는 목적지에 도달하는지 구하는 문제이다.

이전에 BFS문제와 아주 유사하다. 다만 그전에는 한칸씩 상하좌우로 움직였지만 이번에는 좀더 여러방면으로 움직이는 차이가 있다. 이때 가장 적은 움직임의 수를 구해야 하기 때문에 DFS가 아닌 BFS로 풀면 된다.

 

1. BFS를 구현

2. 좌표의 움직임을 구현

3. 이미 움직이거나 움직일 곳은 표시하여 중복을 제거

 

이를 토대로 코드를 구현하면 아래와 같다.

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

def BFS(l, start, end):
    M = [[0 for i in range(l)] for i in range(l)]
    M[start[0]][start[1]] = 1
    q = deque([start])

    dx = [-1,-2,-2,-1,1,2,2,1] # 행
    dy = [-2,-1,1,2,2,1,-1,-2] # 열
    time = -1
    while q:
        time+=1
        for i in range(len(q)):#개수만큼 반복
            x,y =  q.popleft()
            if [x,y] == end:
                return time
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0<=nx<l) and (0<=ny<l) and (M[nx][ny]==0):
                    M[nx][ny] = 1
                    q.append([nx,ny])
    
for _ in range(T):
    l = int(input())
    start = list(map(int, input().split()))
    end = list(map(int, input().split()))
    print(BFS(l, start, end))

이전 BFS와 유사한 점이 많다 보니 큰 어려움 없이 풀 수 있었다.