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

문제

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

입력

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

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

출력

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

 

<코드>

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

int T, l, s_x, s_y, e_x, e_y, ans;
bool map[301][301];
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
queue<tuple<int, int, int>> q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();

    cin >> T;

    while (T--)
    {
        q = queue<tuple<int, int, int>>(); // 큐 새로 할당(비우기)
        for (int i = 0; i < 301; i++) // 맵 초기화
            for (int j = 0; j < 301; j++)
                map[i][j] = false;

        cin >> l;
        cin >> s_x >> s_y; // 시작 좌표
        cin >> e_x >> e_y; // 도착 좌표

        q.push({ s_x,s_y,0 });
        map[s_x][s_y] = true; // 시작점 방문 표시

        while (!q.empty())
        {
            int now_x = get<0>(q.front());
            int now_y = get<1>(q.front());
            int cnt = get<2>(q.front());
            
            q.pop();

            if (now_x == e_x && now_y == e_y)
            {
                ans = cnt;
                break;
            }

            for (int i = 0; i < 8; i++)
            {
                int next_x = now_x + dx[i];
                int next_y = now_y + dy[i];

                // 범위에 벗어나지 않고 방문한 적이 없다면
                if (next_x >= 0 && next_x < l && next_y >= 0 && next_y < l) 
                    if (!map[next_x][next_y])
                    {
                        map[next_x][next_y] = true; // 방문 표시
                        q.push({ next_x ,next_y ,cnt + 1 });
                    }
                        
            }
        }
        cout << ans << '\n';
    }

    
}

 

풀이 방법

 

 

 

 

www.acmicpc.net/problem/7562

7562번: 나이트의 이동