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

문제링크 : https://boj.kr/7562

(시작점) -> (끝점)까지 나이트가 갈 수 있는 경로의 최단거리를 구하는 문제로 이동 가능한 8방향으로 BFS를 돌리면 풀 수 있다.

장애물 없이 오로지 도달만 하면 되기 때문에 방문 체크를 위한 배열 visited만 선언해주었다.

방문 조건은 (0,0) ~ (len-1, len-1)의 범위로만 한정하였다.

// BOJ 7562 나이트의 이동
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
 
struct pt {
    int x, y, cnt;
 
    pt() {
        cnt = 0;
    }
 
    pt(int a, int b, int c) {
        x = a, y = b, cnt = c;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    int tc;
    cin >> tc;
    while (tc--) {
        int len, ans;
        cin >> len;
        vector<vector<int> > visited(len, vector<int>(len, false));
        pt S, E;
        cin >> S.x >> S.y;
        cin >> E.x >> E.y;
        visited[S.x][S.y] = true;
        queue<pt> Q;
        Q.push(S);
        while (!Q.empty()) {
            pt cur = Q.front();
            Q.pop();
            if (cur.x == E.x && cur.y == E.y) {
                ans = cur.cnt;
                break;
            }
            for (int i = 0; i < 8; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                if ((x >= 0 && x < len && y >= 0 && y < len)
                    && !visited[x][y]) {
                    visited[x][y] = true;
                    Q.push({x, y, cur.cnt + 1});
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}