[BFS] BJ16948 데스 나이트

문제 출처: https://www.acmicpc.net/problem/16948

 

Solution

• BFS 탐색을 하며 나이트가 움직일 수 있는 곳들의 거리를 업데이트 해주고, 목적지를 만나면 거리를 리턴한다.

Point

• 최단거리 문제이기 때문에 DFS보다 BFS로 탐색하는 것이 효과적이다.
• 주의할 점은 나이트의 움직임이 일반적이지 않다는 것인데, dr[], dc[] 만 잘 정의해주면 일반적인 최단거리 찾는 문제와 다를 것이 없다.

---

#include <iostream>
#include <queue>

using namespace std;

struct rc { int r, c; };

int N, r1, c1, r2, c2;
int dr[] = { -2, -2, 0, 0, 2, 2 };
int dc[] = { -1, 1, -2, 2, -1, 1 };

int map[200][200];
int dist[200][200];

int bfs() {
    queue<rc> q;
    dist[r1][c1] = 1;
    q.push({ r1, c1});
    while (!q.empty()) {
        rc cur = q.front(); q.pop();
        for (int i = 0; i < 6; i++) {
            int nr = cur.r + dr[i];
            int nc = cur.c + dc[i];
            if (0 <= nr && nr < N && 0 <= nc && nc < N && !dist[nr][nc]) {
                if (nr == r2 && nc == c2) return dist[cur.r][cur.c];
                q.push({ nr, nc });
                dist[nr][nc] = dist[cur.r][cur.c] + 1;
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> r1 >> c1 >> r2 >> c2;
    cout << bfs() << endl;
}