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

문제

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

 

문제 내용

각 테스트 케이스별로 체스판의 길이, 나이트의 현재 위치와 이동하려는 위치가 주어진다.

나이트가 최소로 이동하여 목적지까지 갔을 때, 몇 번의 이동이 필요한지 출력하면 된다.

 

문제 풀이

bfs를 통해 이 문제를 풀면 좋다.

체스판의 길이를 len이라 했을 때 len*len 배열을 선언하고, 초기 위치부터 bfs를 돌리면 된다.

초기 위치의 값을 1로 하고, 해당 위치로부터 갈 수 있는 곳을 +1 하여 배열에 저장하는 방식으로 문제를 풀었다.

그렇게 하면 목적지에 해당하는 arr배열의 값-1 이 구하고자 하는 값이 된다. (시작을 1로 세팅했기 때문에 -1 필요)

 

나이트가 이동할 수 있는 위치는 문제에 주어진 것처럼 8개이다. 

미리 dr, dc 배열로 만들어두면, 반복문을 통해 쉽게 위치를 구할 수 있다.

이때 반드시 배열의 범위를 넘어가는지를 체크해야 한다. 

 

코드

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

int dr[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dc[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int solution() {
    int len;
    cin >> len;

    vector<vector<int>> arr(len, vector<int>(len, 0)); // 0은 이동 전
    queue<pair<int, int>> q;

    int stR, stC;
    cin >> stR >> stC;
    q.push({stR, stC});
    arr[stR][stC] = 1;

    int enR, enC;
    cin >> enR >> enC;

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();

        if (p.first == enR && p.second == enC) {
            break;
        }

        for (int i = 0; i < 8; i++) {
            int nr = p.first + dr[i];
            int nc = p.second + dc[i];

            if (nr >= 0 && nc >= 0 && nr < len && nc < len && arr[nr][nc] == 0) {
                q.push({nr, nc});
                arr[nr][nc] = arr[p.first][p.second] + 1;
            }
        }
    }

    return arr[enR][enC] - 1;
}

int main() {
    int testCase;
    cin >> testCase;

    while (testCase--) {
        cout << solution() << '\n';
    }
}