BOJ - 7562. 나이트의 이동

문제

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

입력

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

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

출력

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

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

---

풀이 과정

• 최소 몇번만에 움직일 수 있냐고 문제에서 물었기에 BFS 탐색을 사용하여 구현하였습니다.
• 나이트가 움직일 수 있는 경우들을 배열로 먼저 표현해놓았습니다.

int dx[]={2,2,1,1,-2,-2,-1,-1};
int dy[]={1,-1,2,-2,1,-1,2,-2};

• 위 방향에 맞추어 이동하다가 target값을 찾게되면 해당 나이트의 이동 횟수를 출력해주면 됩니다.

---

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int chess[301][301];
bool visit[301][301];

int dx[]={2,2,1,1,-2,-2,-1,-1};
int dy[]={1,-1,2,-2,1,-1,2,-2};
int bfs(int size,int y,int x,int targetY,int targetX){
    queue<pair<int,pair<int,int>>> q;

    q.push(make_pair(0,make_pair(y,x)));
    visit[y][x]=true;
    while(!q.empty()){
        int count = q.front().first;
        int curY = q.front().second.first;
        int curX = q.front().second.second;
        if(curY==targetY && curX==targetX){
            return count;
        }
        q.pop();
        for(int i=0;i<8;i++){
            int nextY = curY + dy[i];
            int nextX = curX + dx[i];
            if(nextY<0 || nextX<0 ||nextY>=size ||nextX>=size){
                continue;
            }
            if(visit[nextY][nextX]==false){
                visit[nextY][nextX]=true;
                q.push(make_pair(count+1,make_pair(nextY,nextX)));
            }

        }
    }
    return -1;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        memset(visit,false,sizeof(visit));
        int l,startY,startX, targetY, targetX;
        cin>>l>>startY>>startX>>targetY>>targetX;
        int num = bfs(l,startY,startX,targetY,targetX);
        cout<<num<<'\n';
    }

    return 0;

}