[BOJ/C++] 7562번: 나이트의 이동

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

7562번: 나이트의 이동

[풀이]

나이트가 이동하는 방향만 잘 고려한다면 결국 최단 거리를 찾는 문제와 동일하기 때문에 전형적인 BFS 문제입니다.

다른 기본적인 BFS 최단거리 문제에서 사용하는 상하좌우로 이동 대신 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 목적지까지의 Depth를 찾으면 되는 간단한 문제였습니다.

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

int cnt[300][300];
queue<pair<int, int>> q;
pair<int, int> s, e;
pair<int, int> d[8] = { {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2} };

bool isValid(int n_y, int n_x, int l) {
    return (n_y >= 0 && n_x >= 0 && n_y < l && n_x < l);
}

void bfs(int l) {
    cnt[s.first][s.second] = 1;
    q.push(s);
    while (!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int n_y = node.first + d[i].first;
            int n_x = node.second + d[i].second;
            if (isValid(n_y, n_x, l)) {
                if (!cnt[n_y][n_x]) {
                    cnt[n_y][n_x] = cnt[node.first][node.second] + 1;
                    q.push({ n_y, n_x });
                }
            }
        }
    }
}

int main() {
    int n; cin >> n;
    while (n--) {
        int l; cin >> l;
        cin >> s.first >> s.second;
        cin >> e.first >> e.second;
        memset(cnt, 0, sizeof(cnt));
        bfs(l);
        cout << cnt[e.first][e.second] - 1 << '\n';
    }
}