[백준 7562번] 나이트의 이동 - 파이썬(python)

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이 설계

• 나이트의 이동방향 배열을 설정한다.
• BFS를 실행하기 위해 q와 visit 배열을 만든다.
• 나이트가 움직이려고하는 위치에 도착하면 break하고 해당 cnt를 출력한다.

풀이

from collections import deque

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

T = int(input())
for _ in range(T):
    l = int(input())
    now_x, now_y = map(int, input().split())
    move_x, move_y = map(int, input().split())

    q = deque([(now_x, now_y, 0)])
    visit = [[False] * l for _ in range(l)]
    visit[now_x][now_y] = True

    while q:
        x, y, cnt = q.popleft()
        if x == move_x and y == move_y:
            print(cnt)
            break
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < l and 0 <= ny < l and not visit[nx][ny]:
                visit[nx][ny] = True
                q.append((nx, ny, cnt + 1))

후기

• 한동안 DP위주로 풀다가 오랜만에 BFS푸니까 나름 재미있었다.