[탐색/BFS] 백준 7562 나이트의 이동 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

7562번: 나이트의 이동

 

 

 

2. 문제 풀이

 나이트가 몇 번 이동해야 원하는 지점에 도착하는지 구하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 총 8가지 방향으로 나이트는 이동이 가능합니다. 8개의 방향벡터로 BFS 탐색을 실시합니다.

 

 

 

3. 코드

from collections import deque

# 입력
T = int(input())
for _ in range(T):
    l = int(input())
    s1, s2 = map(int, input().split())
    e1, e2 = map(int, input().split())

    # bfs
    board = [[0]*l for _ in range(l)]
    queue = deque([(s1, s2)])
    board[s1][s2] = 1

    direction = [(-2, -1), (-1, -2), (1, -2), (2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)]
    while queue:
        x, y = queue.popleft()
        if x == e1 and y == e2:
            print(board[x][y]-1)
            break
        for dx, dy in direction:
            nx, ny = x+dx, y+dy
            if 0 <= nx < l and 0 <= ny < l and board[nx][ny] == 0:
                board[nx][ny] = board[x][y] + 1
                queue.append((nx, ny))

 BFS탐색을 진행합니다. 방향벡터만 잘 설정하면 무리 없이 푸실 수 있습니다.