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

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

7562번: 나이트의 이동

문제

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

입력

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

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

출력

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

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

---

 

풀이

• 기존 BFS/DFS에서 사용하는 방향 벡터를 나이트가 이동할 수 있는 8개의 좌표로 지정하여 BFS를 실행하였다.
• 테스트케이스가 여러개일 수 있으므로, 케이스를 입력할 때마다 큐와 2차원 배열을 비워주고 초기화해야 한다.

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 301
#define _X first
#define _Y second

int board[MAX][MAX];
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int t, l; // 테스트 케이스, 한 변의 길이
int posX, posY, tPosX, tPosY;
queue<pair<int, int>> q;

// 배열 초기화, 큐 비워주는 함수
void Reset(int side)
{       
    for (int i = 0; i < side; i++)
    {
        for (int j = 0; j < side; j++)
        {
            board[i][j] = 0;
        }
    }
    while (!q.empty()) q.pop();
}

int Bfs()
{
    while (!q.empty())
    {
        // 이동하려는 좌표가 시작 좌표면 안 움직여도 된다.
        if (posX == tPosX && posY == tPosY) return 0;

        // 현재 위치 x, y 저장
        pair<int, int> cur = q.front();
        int x = cur._X;
        int y = cur._Y;
        q.pop();

        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 벗어나거나 이미 방문했으면 무시
            if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
            if (board[nx][ny] != 0) continue;

            // 다음 위치가 이동하려던 위치면 이동 횟수 반환
            if (nx == tPosX && ny == tPosY) return board[x][y] + 1;
            
            q.push({ nx, ny });
            board[nx][ny] = board[x][y] + 1;
        }
    }
}

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

    cin >> t;

    while (true)
    {
        // 테스트 케이스 횟수만큼 다 입력하면 반복문 벗어나기
        if (t == 0) break;  
        cin >> l;
        Reset(l);

        cin >> posX >> posY >> tPosX >> tPosY;
        // 현재 위치 큐에 넣고 Bfs 실행 후 이동 횟수 출력
        q.push({ posX, posY });
        int result = Bfs();
        cout << result << '\n';
        t--;
    }

    return 0;
}