백준 알고리즘 7562번 나이트의 이동

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

문제

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

입력

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

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

출력

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

풀이

체스 판의 한변 길이, 현재 칸의 좌표, 이동하려고 하는 칸의 좌표를 입력받는다. 입력받은 것들을 bfs라는 함수로 보내서 BFS를 통해 현재 칸에서 갈 수 있는 경우들을 각각 확인하고 가면서, 현재 칸으로부터 몇 번 이동했는지도 센다. 이동하려는 칸이 나오면, 시작한 칸으로부터 몇 번만에 간 것인지 바로 리턴한다.

나이트가 한 칸에서 이동할 수 있는 칸은 8개가 있다. 각각을 가보고 확인하는 방법으로 처음에는 8개의 if 문을 썼었는데, 더 간단한 방법으로 x좌표, y좌표로 갈 수 있는 거리를 값으로 가진 배열을 만드는 방법을 알게되었다. 8개 각각의 칸에 대해 해야할 일은 같기 때문에 for 문을 통해 할 수 있다.

체스 판의 크기를 벗어나지 않고 방문하지 않은 경우, 큐에 넣고 몇 번만에 왔는지 세고 방문표시를 해주었다. 그리고 이동하려는 칸이 나오면 몇 번만에 왔는지를 리턴해준다.

코드

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

int bfs(int size, int startX, int startY, int finalX, int finalY) {

    int arrayX[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int arrayY[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int visit[size][size]; // 0: 미방문, 1: 방문
    int count[size][size]; // 
    queue <pair<int, int>> que;

    for (int i=0;i<size;i++) {
        for (int j=0;j<size;j++) {
            visit[i][j] = 0;
            count[i][j] =-1;
        }
    }

    que.push(make_pair(startX, startY));
    count[startX][startY] = 0;

    while (!que.empty()) {
        int a = que.front().first;
        int b = que.front().second;
        visit[a][b] = 1;

        que.pop();

        for (int i=0;i<8;i++) {
            if (a+arrayX[i] >= 0 && a+arrayX[i] < size && b+arrayY[i] >= 0 && b+arrayY[i] < size) {
                if (visit[a+arrayX[i]][b+arrayY[i]] == 0) { 
                    
                    que.push(make_pair(a+arrayX[i], b+arrayY[i])); 
                    count[a+arrayX[i]][b+arrayY[i]] = count[a][b] + 1;
                    visit[a+arrayX[i]][b+arrayY[i]] = 1;

                    if (a+arrayX[i] == finalX && b+arrayY[i] == finalY) {
                       return count[a+arrayX[i]][b+arrayY[i]];
                    }
                }
            }
        }

    }
    return 0;
    
}

int main() {

    int NUM, count, i=0;
    int size, startX, startY, finalX, finalY;

    cin >> NUM;
    int answer[NUM];

    while (NUM--) {
        cin >> size >> startX >> startY >> finalX >> finalY;

        count = bfs(size, startX, startY, finalX, finalY);
        
        answer[i++] = count;

    }

    for (int j=0;j<i;j++) {
        cout << answer[j] << endl;
    }

    return 0;
}