[Baekjoon/C++] 16948번 - 데스 나이트

[백준] Baekjoon Online Judge

문제로 이동

 

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

 

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

 

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

---

풀이

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

int N, r1, c1, r2, c2;
bool check[201][201];

void bfs();
bool canVisit(int r, int c);

void bfs() {
    queue<pair<pair<int, int>, int>> q;

    q.push({ { r1, c1 }, 0 });
    check[r1][c1] = true;

    while (!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int cnt = q.front().second;
        q.pop();

        // 최종 목적지 도착
        if (r == r2 && c == c2) {
            cout << cnt << '\n';
            exit(0);
        }

        // 데스 나이트 이동 경우의 수
        int nr[6] = { r - 2, r - 2, r, r, r + 2, r + 2 };
        int nc[6] = { c - 1, c + 1, c - 2, c + 2, c - 1, c + 1 };

        for (int i = 0; i < 6; i++) {
            if (canVisit(nr[i], nc[i])) {
                q.push({ { nr[i], nc[i] }, cnt + 1 });
                check[nr[i]][nc[i]] = true;
            }
        }
    }
}

// 방문 가능 여부 체크
bool canVisit(int r, int c) {
    return ((r <= N && r >= 0) && (c <= N && c >= 0) && !check[r][c]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> r1 >> c1 >> r2 >> c2;

    bfs();

    cout << "-1\n";

    return 0;
}

너비 우선 탐색을 사용하여 문제를 풀었다.

 

void bfs() {
    queue<pair<pair<int, int>, int>> q;

    q.push({ { r1, c1 }, 0 });
    check[r1][c1] = true;

    while (!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int cnt = q.front().second;
        q.pop();

        // 최종 목적지 도착
        if (r == r2 && c == c2) {
            cout << cnt << '\n';
            exit(0);
        }

        // 데스 나이트 이동 경우의 수
        int nr[6] = { r - 2, r - 2, r, r, r + 2, r + 2 };
        int nc[6] = { c - 1, c + 1, c - 2, c + 2, c - 1, c + 1 };

        for (int i = 0; i < 6; i++) {
            if (canVisit(nr[i], nc[i])) {
                q.push({ { nr[i], nc[i] }, cnt + 1 });
                check[nr[i]][nc[i]] = true;
            }
        }
    }
}

queue를 사용하여 구현한 너비 우선 탐색 함수이다. 데스 나이트 이동 경우의 수를 미리 계산해서 배열에 넣고, for문으로 이를 사용하였다. 그러다가 최종 목적지에 도착한다면 답을 출력하고, 프로그램이 종료되게끔 했다. 만약 해당 함수가 종료될 때까지 최종 목적지에 도착하지 못한다면 main 함수의 cout이 실행된다.

 

// 방문 가능 여부 체크
bool canVisit(int r, int c) {
    return ((r <= N && r >= 0) && (c <= N && c >= 0) && !check[r][c]);
}

해당 칸이 방문 가능한 칸인지 체크하는 함수이다. bfs()에서 위의 조건들을 if문 안에 쓰니 가독성이 좋지 않았기에 따로 함수로 만들어서 사용하였다.