(매일 BOJ) C++ 7562번 나이트의 이동

이번 문제는 7562번 나이트의 이동이다

문제 요약

체스판 한 변의 길이 I가 주어지고, 나이트의 시작 좌표 (x, y)와 목표 좌표 (nx, ny)가 주어진다
나이트가 시작점에서 목표점까지 최소 몇 번 이동하면 도착하는지 출력
테스트케이스가 여러 개 주어진다

• 체스판 좌표는 0 ~ I-1 (열/행 헷갈리지 않게 한 가지 규칙으로만 쓰면 됨)
• 나이트 이동: 8방향
  (-2,-1), (-2, 1), (-1,-2), (-1, 2), (1,-2), (1, 2), (2,-1), (2, 1)

접근법

이 문제는 간선 가중치가 모두 1인 격자 최단거리 문제 → BFS가 정석이다

• dist(혹은 방문 겸 거리 배열)를 -1로 초기화: 미방문 표기
• 시작칸은 0으로 두고 큐에 넣는다
• 큐를 돌며 현재 칸에서 나이트 이동 8방을 확장
• 처음으로 목표칸을 생성/방문하는 순간의 거리 값이 곧 최소 이동 횟수

BFS는 레벨 순(=이동 횟수 순)으로 확장하므로, 목표를 가장 먼저 만나면 그때가 최단이다.

구현 포인트

• 방문 체크와 거리 저장을 한 배열로 통합(미방문 = -1, 시작 = 0)
• 경계 체크: 0 <= nx, ny < I
• 조기 종료: 목표 칸을 만들어내는 순간 바로 반환하면 쓸데없는 탐색을 줄일 수 있다
• 테스트케이스마다 보드를 새로 만들기

 

작성코드

#include <bits/stdc++.h>
using namespace std;

int BFS (int x, int y, int nx, int ny, vector<vector<int>> & chessboard, int I);
int eightway_x[8] = {-2,-2,-1,-1,1,1,2,2};
int eightway_y[8] = {-1,1,-2,2,-2,2,-1,1};

int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    int test_case;
    cin >> test_case;

    for(int i = 0; i < test_case; i++){
        int I;
        cin >> I;
        vector<vector<int>> chessboard (I,vector<int>(I,-1));
        int x,y;
        cin >> x >> y;
        int nx,ny;
        cin >> nx >> ny;
        int answer = BFS(x,y,nx,ny,chessboard, I);
        cout << answer << '\n';
    }

    return 0;
}

int BFS (int x, int y, int end_x, int end_y, vector<vector<int>> & chessboard, int I){
    chessboard[x][y] = 0;
    if(x == end_x && y == end_y) return 0;
    queue<pair<int,int>> q;
    q.push({x,y});

    while(!q.empty()){
        int current_x = q.front().first;
        int current_y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++){
            int next_x = eightway_x[i] + current_x;
            int next_y = eightway_y[i] + current_y;

            if(next_x >= 0 && next_y >= 0 && next_x < I && next_y < I && chessboard[next_x][next_y] == -1){
                chessboard[next_x][next_y] = chessboard[current_x][current_y] + 1;
                q.push({next_x,next_y});
            }

            if(next_x == end_x && next_y == end_y) return chessboard[end_x][end_y];
        }
    }
    return chessboard[end_x][end_y];
}