문제 출처 : https://www.acmicpc.net/problem/7562
난이도 : 실버 1

---

문제 파악

체스판 위에서 나이트(Knight) 가 이동한다.

나이트는 한 번에

• (±1, ±2)
• (±2, ±1)

총 8가지 방향으로만 이동 가능하다.

각 테스트케이스마다

• 체스판 한 변의 길이 I
• 시작 좌표 (start_x, start_y)
• 도착 좌표 (end_x, end_y)

가 주어질 때, 최소 몇 번 이동해야 도착하는지를 출력하는 문제다.

---

“최소 이동 횟수”를 구해야하므로 BFS 으로 풀 수 있었고
visited 배열을 따로 만들지 않고 board 변수 안에 방문 여부 체크, 최단 이동 횟수 저장 동시에 코드를 구현했다.

• board[y][x] = -1 : 아직 방문 안 함
• board[y][x] = k : 해당 칸까지 k번만에 도착(=거리)

해답 및 풀이

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

# 나이트의 이동 방향 벡터 , 나이트는 총 8방향으로 움직일 수 있다.
dx = [-1,-2,-2,-1,1,2,2,1]
dy = [-2,-1,1,2,2,1,-1,-2]

def bfs(start_x,start_y,end_x,end_y,board,I):
    queue = deque()
    queue.append((start_x, start_y))
    board[start_y][start_x] = 0 

    while queue:
        x, y = queue.popleft()

        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < I and 0 <= ny < I and board[ny][nx] == -1: # 범위내 존재하고, 미방문
                board[ny][nx] = board[y][x] + 1
                queue.append((nx,ny))

            elif nx == end_x and ny == end_y:
                return board[ny][nx]

T = int(input())

for _ in range(T):

    # I = 체스판 한 변의 길이
    I = int(input())

    # board= I x I 체스판
    board = [
        [-1] * I for _ in range(I)
    ]

    # 출발점 x, y 
    start_x, start_y = map(int,input().split())

    # 도착점 x, y 
    end_x, end_y = map(int,input().split())
    print(bfs(start_x, start_y, end_x, end_y, board, I))

---

다음날 풀어본 답

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

# 나이트의 이동 방향 벡터 , 나이트는 총 8방향으로 움직일 수 있다.
dx = [-1,-2,-2,-1,1,2,2,1]
dy = [-2,-1,1,2,2,1,-1,-2]

def bfs(I,graph,start_x, start_y, end_x, end_y):

    if start_x == end_x and start_y == end_y:
        print(0)
        return 
    
    queue = deque()
    queue.append((start_x,start_y))
    
    while queue:
        x, y= queue.popleft()

        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]  

            if 0 <= nx < I and 0 <= ny < I and graph[ny][nx] == 0: # 범위 내 존재, 방문 X
                graph[ny][nx] = graph[y][x] + 1 # 이동거리 1 추가
                queue.append((nx,ny))
            
            elif ny == end_y and nx == end_x:
                print(graph[end_y][end_x])
                return
                

T = int(input())
for _ in range(T):
    I = int(input())
    graph = [[0] * I for _ in range(I)]
    start_x, start_y = map(int,input().split())
    end_x, end_y = map(int,input().split())
    
    # 최소 이동 거리 출력
    bfs(I,graph,start_x, start_y, end_x, end_y)