오늘의 알고리즘 - boj-7562

문제

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

풀이

BFS를 단순하게 4방향으로 돌리는게 아니라 나이트의 이동방향을 설정 해줘야 하는 문제였다.

그래서 시계방향으로 나이트의 이동방향을 설정했고 directions라는 테이블에 담아 direction이라는 이름으로 추출했다.

그리고 스타트값을 큐에 담아줄 때 cnt값을 추가로 넣어주고 그 값을 통해서 현재 나이트를 몇번 움직였는지 체크해준다.

마지막으로 cur_node를 추출했을 때 그 값이 end값과 같다면 cnt값을 리턴해서 답을 얻었다.

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



def get_moving_time(start:list[int], end:list[int]) -> int:
    queue = deque()
    queue.append(start+[0])
    visited[start[0]][start[1]] = 1
    
    while queue:
        cur_node = queue.popleft()
        
        if cur_node[:2] == end: return cur_node[2]
        
        cur_row, cur_col, cnt = cur_node[0], cur_node[1], cur_node[2]
        
        for direction in directions:
            next_row = cur_row + direction[0]
            next_col = cur_col + direction[1]
            
            if 0 <= next_row < N and 0<= next_col < N and not visited[next_row][next_col]:
                visited[next_row][next_col] = 1
                queue.append([next_row, next_col, cnt + 1])
                

if __name__ == "__main__":                
    T = int(input())
    directions = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]] 
    for _ in range(T):
        N = int(input())
        start = list(map(int, input().split()))
        end = list(map(int , input().split()))
        visited = [[0] * N for _ in range(N)]

        print(get_moving_time(start = start, end = end))