[BOJ / C++] 7562번 : 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

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

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

출력

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

Solved.ac 레벨

실버I

풀이

#include <bits/stdc++.h>
#define MAX 301

using namespace std;

int t, lenChess; 
int kx, ky, nkx, nky; //knightx, y / nextKnightx, y
int chess[MAX][MAX];
bool visitied[MAX][MAX];
int dx[8] = {-2, -2, 2, 2, -1, -1, 1, 1};
int dy[8] = {-1, 1, -1, 1, -2, 2, -2, 2};
queue< pair<int, int> > q;

void BFS(int x, int y){
    visitied[x][y] = true;
    q.push(make_pair(x, y));

    while(!q.empty()){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        if(curX == nkx && curY == nky){
                cout << chess[curX][curY] << '\n';

                while(!q.empty()){
                    q.pop();
                }
                break;
        }

        for(int i = 0; i < 8; i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];

            

            if(nextX >= 0 && nextX < lenChess && nextY >= 0 && nextY < lenChess){
                if(!visitied[nextX][nextY]){
                    chess[nextX][nextY] = chess[curX][curY] + 1;
                    visitied[nextX][nextY] = true;
                    q.push(make_pair(nextX, nextY));
                }
            }
        }
        
    }

}

void reset(){
    memset(chess, 0, sizeof(chess));
    memset(visitied, false, sizeof(visitied));
    lenChess = 0; kx = 0; ky = 0; nkx = 0; nky = 0;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    
    while(t--){
        
        cin >> lenChess;
        
        cin >> kx >> ky >> nkx >> nky;

        BFS(kx, ky);

        reset();
    }
    
    return 0;
}

평소 상하좌우 방향으로 탐색하던 것을 나이트의 이동 방식으로 바꾸어주기만 하면 되는 문제다.

평소에는 뭐가 심어져있다던가, 뭐가 벽이든가 하는 문제여서 map을 다 채워줄 수 있었지만, 이번 문제는 기존과 달리 시작 좌표에서 해당 좌표까지 이동할 때 필요한 횟수를 저장해두었다.

 

7562번: 나이트의 이동