알고리즘 스터디 - 백준 7562번 : 나이트의 이동

문제 해석

• 체스판 위 나이트로 움직일 수 있는 칸이 있다.
• 나이트로 특정 칸으로 이동할 때 횟수

입력

1. 테스트 케이스의 개수
2. 체스판의 한변의 길이 l -> 체스판의 크기 lxl
3. 나이트의 현재 위치
4. 나이트가 이동하려는 칸
5. 테스트 케이스만큼 2~4 반복

어떤 알고리즘을 써야할까?

나이트의 이동 패턴

(0, 0) -> (1, 2), (2, 1), (2, -1), (1, -2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)

• 여기서 알 수 있는 것은 |x| + |y| = 3 (|x| = 1 or 2, |y| = 2 or 1)

0 0
7 0

• 이 경우 (0, 0) -> (0+2, 0+1) -> (0+2+2, 0+1-1) -> (0+2+2+2, 0+1-1+1) -> (0+2+2+2+2, 0+1-1+1+1) -> (0+2+2+2+2-1, 0+1-1+1+1-2)로 총 5번이 발생한다.
• 즉, x와 y가 정해진 규칙에 따라서 움직이게 된다.

기존에 좌표 이동시 사용했던 방식을 이용해 한번 구해보자. 영역 구하기

알고리즘 코드

test_case = int(input())

def find_minimum_number(initial_x, initial_y, target_x, target_y, length):
    # 좌표선언
    matrix = [[False for _ in range(length)] for _ in range(length)]
    matrix[initial_x][initial_y] = True

    # 나이트가 움직이는 패턴
    dx = [2, 2, -2, -2, 1, 1, -1, -1]
    dy = [1, -1, 1, -1, 2, -2, 2, -2]

    # 큐 선언
    q = []

    # 초기 값 삽입
    q.append((initial_x, initial_y, 0))

    while q:
        x_, y_, number = q.pop(0)

        if x_ == target_x and y_ == target_y:
            return number
        
        for i in range(8):
            new_x = x_ + dx[i]
            new_y = y_ + dy[i]

            if 0 <= new_x < length and 0 <= new_y < length and not matrix[new_x][new_y]:
                matrix[new_x][new_y] = True
                q.append((new_x, new_y, number + 1))

for _ in range(test_case):
    length = int(input())
    initial_x, initial_y = map(int, input().split())
    target_x, target_y = map(int, input().split())

    print(find_minimum_number(initial_x, initial_y, target_x, target_y, length))