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

분류: bfs /

 

문제 

문제 링크

문제 설명

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

입력

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

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

출력

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

 

풀이

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct xy { int x, y; };
int board[300][300];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};

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

    int T; cin >> T;
    while(T--) {
        int n, x, y; 
        cin >> n;
        for(int i=0; i<n; i++) 
            fill(board[i], board[i]+n, -1);

        cin >> x >> y;
        board[x][y] = 0;
        queue<xy> Q;
        Q.push({x, y});

        cin >> x >> y;
        while(!Q.empty() && board[x][y] == -1) {
            xy cur = Q.front(); Q.pop();
            for(int d=8; d--;) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                if(board[nx][ny] != -1) continue;
                board[nx][ny] = board[cur.x][cur.y] + 1;
                Q.push({nx, ny});
            }
        }
        cout << board[x][y] << '\n';
    }
}