백준 7562 나이트의 이동 - C++

 

접근

나이트가 있는 위치 기준(x,y)으로 나이트가 이동할 수 있는 위치는

(x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2), (x+1, y+2), (x+2, y+1), (x+2, y-1), (x+1, y-2) 이런식이다.

1. 주어진 x,y를 기점으로 갈 수 있는 곳에 표시를 한다.

 - bfs 탐색 알고리즘을 활용하여 똑같은 위치를 방문하지 않도록 한다. 

 - 똑같은 위치는 0인지 아닌지로 판별한다.(0이면 아직 방문하지 않음)

 - 현재 위치에서 다음 위치로 이동할 때는 현재 위치 +1을 한다. 

2. 계속 방문 하다가 현재 위치가 도착지 위치와 동일하면 얼마나 걸렸는지 출력

 

#include <iostream>
#include <queue>
using namespace std;
int A[301][301];
int low[] = {-1, -1, +1, +1, -2, -2, +2, +2};
int col[] = {-2, +2, -2, +2, -1, +1, -1, +1};
int Len;

int bfs(int i, int j, int desI, int desJ){
    queue<pair<int, int>> q;
    q.push(make_pair(i,j));

    int curI, curJ;
    while(!q.empty()){
        curI = q.front().first;
        curJ = q.front().second;
        q.pop();
        if(curI == desI && curJ == desJ) return A[curI][curJ];
        //나이트가 갈 수 있는 (행,열) 총 8번 비교
        for(int i=0; i<8; i++){
            int valI = curI+low[i];
            int valJ = curJ+col[i];
            if( ( valI >= 0 && valI < Len)  && (valJ >= 0 && valJ < Len) ){ 
                if(A[valI][valJ] == 0 ){
                    q.push(make_pair(valI,valJ));
                    A[valI][valJ] = A[curI][curJ]+1;
                } 
            }
        }
    }

    return 0;
}

int main()
{   
    int T;
    cin >> T;
    while(T--){
        cin >> Len;
        for(int i=0; i<Len; i++){
            for(int j=0; j<Len; j++){
                A[i][j] = 0;
            }
        }
        int startI, startJ, desI, desJ;
        cin >> startI >> startJ;
        cin >> desI >> desJ;
        int cnt = bfs(startI, startJ, desI, desJ);
        cout << cnt << '\n';
    }
    return 0;
}