백준 알고리즘 7562번 : 나이트의 이동

Zoo Da·2021년 7월 6일

BFS 백준 알고리즘

백준 알고리즘

목록 보기

95/337

링크

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

문제

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

입력

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

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

출력

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

예제 입력 및 출력

풀이 코드(C++)

// 7562번 : 나이트의 이동(실버 2)

#include <iostream>
#include <queue>
#include <cstring>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX 300
using namespace std;

int graph[MAX][MAX] = {
    0,
}; // 인접 행렬 그래프
bool visit[MAX][MAX] = {
    false,
};

int l, sX, sY, dX, dY;                   // sx : 출발 x좌표, sy : 출발 y좌표, dx : 도착 x좌표, dy : 도착 y좌표, l : 그래프의 최대 크기
int dx[] = {2, 1, 2, 1, -1, -2, -2, -1}; // 8방향 x좌표 탐색
int dy[] = {1, 2, -1, -2, 2, 1, -1, -2}; // 8방향 y좌표 탐색
queue<pair<int, int>> Q;

//최단 거리를 구해야 하기 때문에 bfs를 사용

void bfs(int x, int y)
{
    visit[x][y] = true;
    while (!Q.empty())
    {
        auto cur = Q.front();
        visit[cur.first][cur.second] = true;
        Q.pop();
        for (int i = 0; i < 8; i++)
        {
            int newX = cur.first + dx[i];
            int newY = cur.second + dy[i];
            if (newX < 0 || newX >= l || newY < 0 || newY >= l)
                continue;
            if (visit[newX][newY] == false && graph[newX][newY] == 0)
            {
                graph[newX][newY] = graph[cur.first][cur.second] + 1;
                visit[newX][newY] = true;
                Q.push(make_pair(newX, newY));
            }
        }
    }
}

int main()
{
    fastio;
    int tc; // 테스트 케이스
    cin >> tc;
    for (int i = 0; i < tc; i++)
    {
        cin >> l;
        cin >> sX >> sY;
        graph[sX][sY] = 1;
        Q.push(make_pair(sX, sY));
        cin >> dX >> dY;
        if (sX == dX && sY == dY)
        {
            cout << '0' << "\n";
            continue;
        }
        bfs(sX, sY);
        cout << graph[dX][dY] - 1 << "\n";
        memset(graph, 0, sizeof(graph));
        memset(visit, false, sizeof(visit));
    }
    return 0;
}