체스판 크기와 나이트의 시작/도착 위치를 입력받는다.

나이트가 이동할 수 있는 8가지 방향의 좌표 변화량을 배열로 미리 준비한다.

최소 이동 횟수를 기록할 배열을 만들고 큐에 시작 좌표를 넣는다.

큐가 빌 때까지 반복하며 가장 앞에 있는 좌표를 하나씩 꺼낸다.

꺼낸 좌표가 도착점과 일치하면 기록된 이동 횟수를 출력하고 프로그램을 종료한다.

현재 위치에서 갈 수 있는 8방향을 하나씩 계산한다.

계산한 위치가 체스판 범위 내에 있고 아직 방문하지 않은 곳인지 확인한다.

조건에 맞다면 이전 이동 횟수에 1을 더해 저장하고 해당 좌표를 다시 큐에 넣는다.







#include <iostream>
#include <queue>

using namespace std;

int N, M, r1, c1, r2, c2;
int dist[105][105];
int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};

int main() {
    cin >> N >> M >> r1 >> c1 >> r2 >> c2;

    queue<pair<int, int>> q;
    q.push({r1, c1});
    dist[r1][c1] = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        if (cur.first == r2 && cur.second == c2) {
            cout << dist[cur.first][cur.second];
            return 0;
        }
        for (int i = 0; i < 8; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (ny >= 1 && ny <= N && nx >= 1 && nx <= M) {
                if (dist[ny][nx] == 0) { // 아직 안 가본 곳이라면
                    dist[ny][nx] = dist[cur.first][cur.second] + 1;
                    q.push({ny, nx});
                }
            }
        }
    }
    return 0;
}