[BOJ 백준] 16948번 데스 나이트

문제

BOJ 16948 : https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

접근

BFS를 통해 데스 나이트가 이동 가능한 경로를 모두 탐색하여 (r1, c1)에서 (r2, c2)로 이동이 가능한지 검사해 보았다.

코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n;
    pair<int, int> a, b;
    cin >> n >> a.first >> a.second >> b.first >> b.second;
    int dx[] = {-2, -2, 0, 0, 2, 2};
    int dy[] = {-1, 1, -2, 2, -1, 1};

    int map[200][200];
    int dist[200][200];
    queue<pair<int, int>> q;
    dist[a.first][a.second] = 1;
    q.push(a);
    while (!q.empty()) {
        pair<int, int> front = q.front();
        q.pop();
        for (int i = 0; i < 6; i++) {
            int newx = front.first + dx[i];
            int newy = front.second + dy[i];
            if (0 <= newx && newx < n && 0 <= newy && newy < n && !dist[newx][newy]) {
                if (newx == b.first && newy == b.second) {
                    cout << dist[front.first][front.second];
                    return 0;
                }
                q.push({newx, newy});
                dist[newx][newy] = dist[front.first][front.second] + 1;
            }
        }
    }
    cout << -1;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study