백준 7562 나이트의 이동 c++

문제 출처 : www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제

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

입력

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

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

출력

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

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

정점에서 이동할 수 있는 칸(dir 배열)이 많아진것 뿐인 bfs 기본 문제이다.

이동한 칸마다, 전 칸에 도착한 시간에서 1을 더해준다.

이동하지 않는 경우에도 graph에는 1로 되어있으니 출력에선 1을 빼준다.

코드

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int graph[300][300];
int dir[8][2] = { {1,2},{2,1},{1,-2},{2,-1},{-1,2},{-2,1},{-1,-2},{-2,-1} };
int n,sx,sy,fx,fy;
queue<pair<int,int>> q;
void bfs() {
    q.push({ sx, sy });

    while (!q.empty()) {
        int x, y;
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if (xx >= 0 && xx < n&&yy >= 0 && yy < n && !graph[xx][yy]) {
                q.push({ xx,yy });
                graph[xx][yy] = graph[x][y] + 1;
            }
        }
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> sx >> sy >> fx >> fy;
        graph[sx][sy] = 1;
        bfs();
        cout << graph[fx][fy]-1 << '\n';
        memset(graph, 0, sizeof(graph));

    }

    return 0;
}