[ C++ ] #7562 나이트의 이동 (실버 I)

https://www.acmicpc.net/problem/7562

문제

---

체스판 위에 한 나이트가 놓여져 있다.

나이트가 한 번에 초록색 칸으로 이동할 수 있다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l 이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄에는 나이트가 현재 있는 칸, 셋째 줄에는 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이

---

이는 BFS를 이용하여 경우의수를 살펴보면된다.

현재 나이트의 위치를 처음 Q에 넣고 해당 위치에서 나이트가 이동할수있는 8가지 경우의 수를 모두 살핀다.

몇 번 이동했는지도 생각해야하기 때문에 말의 위치를 pair 로 저장하고 말의 위치와 횟수를 또 pair로 저장한다.

한번 확인한 칸은 다시 확인할 필요없으므로 check 배열을 두고 확인여부를 작성한다.

코드

#include <iostream>
#include <queue>

using namespace std;

int main(){

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n=0; //반복횟수
    cin>>n;

    int w, x, y, fx, fy;
    int dx[8] = {2,2,-2,-2, 1,-1,1,-1};
    int dy[8] = {1,-1,1,-1, 2,2,-2,-2};

    for(int i=0; i<n;i++){ //테이스케이스

        //cout<<i<<"번 째"<<endl; //test
        queue<pair<int, pair<int, int> > > Q;

        cin>>w>>x>>y>>fx>>fy;

        int** check = new int*[w];
        for(int x=0;x<w;x++){
            check[x]= new int[w];
        }

        for (int a = 0; a < w; a++) {
            for (int b = 0; b < w; b++) {
                check[a][b] = 0;
            }
        }
    
        int num=0; //반복횟수
    
        Q.push(make_pair(num, make_pair(x,y)));
        check[x][y]=1;

        int flag=1;
        while(flag){ //BFS
            
            pair<int, int> temp = Q.front().second;
        
            if(temp.first==fx && temp.second==fy){
                    cout<<Q.front().first<<"\\n";
                    flag=0;
                    break;
            }
            //cout<<"pop : ( "<<temp.first<<", "<<temp.second<<" ) "<<Q.front().first<<"\\n";
            int front_num=Q.front().first;
            Q.pop();
            num++;

            for(int a=0;a<8;a++){
                int temp_x = temp.first+dx[a];
                int temp_y = temp.second+dy[a];

                if(temp_x<0 || temp_x >=w || temp_y<0 || temp_y>=w){
                    continue;
                }else{
                    //cout<<"push : ( "<<temp_x<<", "<<temp_y<<" ) "<<num<<"\\n";
                    if(check[temp_x][temp_y]!=1){
                        Q.push(make_pair(front_num+1, make_pair(temp_x, temp_y)));
                        check[temp_x][temp_y]=1;
                    }
                
                }
            }
        }
    }
    return 0;
}