[ BOJ 7562 ] 나이트의 이동 (Python)

문제

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

bfs의 대표적인 문제라고 할 수 있겠다.

문제 풀이

1. dx, dy 배열에 나이트가 이동할 수 있는 칸을 정의한다.
2. queue에 (x 좌표, y 좌표, 이동한 횟수) 를 넣어줄 것이다.
3. 방문 체크를 해주어서 이미 방문한 곳은 다시 방문하지 않는다.

코드

import sys
from collections import deque
input = sys.stdin.readline


T = int(input().rstrip())
for _ in range(T):
    l = int(input().rstrip())
    start_x, start_y = map(int,input().rsplit())
    end_x, end_y = map(int,input().rsplit())
    visited = [[0] * l for _ in range(l)]
    visited[start_x][start_y] = 1

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

    queue = deque()
    queue.append((start_x,start_y,0))

    while (queue):
        #print(queue)
        temp = queue.popleft()
        x, y = temp[0],temp[1]

        if x == end_x and y == end_y:
            print(temp[2])
            break
        
        for i in range(8):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < l and 0 <= ny < l and visited[nx][ny]==0:
                visited[nx][ny] = 1
                queue.append((nx,ny,temp[2]+1))