[백준/BOJ] 7562번: 나이트의 이동 (C++)

문제

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

 

문제 이해

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력과 출력

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l (4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

입출력 예제

 

풀이

이 문제는 BFS를 이용해서 풀 수 있다.

먼저, 나이트의 이동 횟수를 저장할 수 있는 배열과 나이트의 이동방향을 선언했다. 그리고 테스트 케이스마다 visit 배열을 초기화하는 함수를 작성했다.

int T, l;
int sr, sc, er, ec; // 출발 위치, 도착 위치
int visit[301][301];
int dr[8] = { -1,-2,-2,-1,1,2,2,1 };
int dc[8] = { -2,-1,1,2,-2,-1,1,2 };

void init() {
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            visit[i][j] = 0;
        }
    }
}

 

처음 위치 {sr, sc}를 queue에 저장하고 visit[sr][sc]에 1을 저장해서 방문했다고 표시해둔다.

현재 위치를 {nowr, nowc}라고 하면 다음 위치 {nextr, nextc}는 현재 위치에 나이트의 이동방향을 더한 것이다. 이때, 다음 위치 {nextr, nextc}가 범위를 벗어나지 않았거나 방문하지 않았으면 현재 위치에서의 이동 횟수 visit[nowr][nowc]에 1을 더해 이동 횟수를 저장하고 다음 위치를 queue에 넣는다.

void bfs() {
    queue<pair<int, int>> q;
    q.push({ sr,sc });
    visit[sr][sc] = 1;

    while (!q.empty()) {
        int nowr = q.front().first;
        int nowc = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++) {
            int nextr = nowr + dr[i];
            int nextc = nowc + dc[i];
            // 범위 확인
            if (nextr < 0 || nextr >= l || nextc < 0 || nextc >= l) continue;
            // 방문 확인
            if (visit[nextr][nextc]) continue;

            // 이동 횟수 저장
            visit[nextr][nextc] = visit[nowr][nowc] + 1;
            q.push({ nextr,nextc });
        }
    }
}

 

main 함수에서 답을 출력할 때에는 visit[er][ec]에서 1을 뺀 후 출력한다.

int main() {
    cin >> T;
    while (T--) {
        cin >> l;
        cin >> sr >> sc >> er >> ec;
        if (sr == er && sc == ec) {
            cout << "0\n";
            continue;
        }

        bfs();
        cout << visit[er][ec] - 1 << '\n';
        init();
    }
    return 0;
}

 

전체 코드

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

int T, l;
int sr, sc, er, ec;
int visit[301][301];
int dr[8] = { -1,-2,-2,-1,1,2,2,1 };
int dc[8] = { -2,-1,1,2,-2,-1,1,2 };
void init() {
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            visit[i][j] = 0;
        }
    }
}
void bfs() {
    queue<pair<int, int>> q;
    q.push({ sr,sc });
    visit[sr][sc] = 1;

    while (!q.empty()) {
        int nowr = q.front().first;
        int nowc = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++) {
            int nextr = nowr + dr[i];
            int nextc = nowc + dc[i];
            if (nextr < 0 || nextr >= l || nextc < 0 || nextc >= l) continue;
            if (visit[nextr][nextc]) continue;
            visit[nextr][nextc] = visit[nowr][nowc] + 1;
            q.push({ nextr,nextc });
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;
    while (T--) {
        cin >> l;
        cin >> sr >> sc >> er >> ec;
        if (sr == er && sc == ec) {
            cout << "0\n";
            continue;
        }

        bfs();
        cout << visit[er][ec] - 1 << '\n';
        init();
    }
    return 0;
}