백준 7562 - 나이트의 이동 (Python3)

코드

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

for i in range(T):
    n = int(input()) #체스판 길이

    # 체스판 입력
    graph = [[0 for _ in range(n)] for _ in range(n)]
    
    x1, y1 = map(int, input().split()) # 시작 점
    x2, y2 = map(int, input().split()) # 도착 점

    # BFS 구현
    def bfs(x1, y1):
        q = deque()
        q.append((x1, y1))

        # 시작 점 방문 처리
        graph[x1][y1] = 1

        # 나이트가 움직일 수 있는 방향을 표현
        dx = [1, 2, 1, 2, -1, -2, -1, -2]
        dy = [2, 1, -2, -1, 2, 1, -2, -1]

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

            # 도착지에 도착한 경우 return
            if x == x2 and y == y2:
                print(graph[x2][y2] - 1)
                return

            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]

                # 체스판을 벗어나지 않은 경우와
                # 방문하지 않은 경우에만 방문 처리
                if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
                    q.append((nx, ny))

                    # 이전 값에 +1 => 이동 횟수
                    graph[nx][ny] = graph[x][y] + 1
                
    bfs(x1, y1)                

문제 해설

BFS 문제.

미로 탐색과 매우 유사한 문제이다. 움직일 수 있는 값을 가르키는 dx, dy의 값만 정확하게 정해주어 문제를 풀면 미로 탐색과 별 차이 없이 쉽게 풀 수 있으므로 미로 탈출 문제로 설명을 대신하겠습니다!!!