백준 7562번 - 나이트의 이동 (C++)

문제

알고리즘 분류 : 너비 우선 탐색(BFS)

 

접근 방법

BFS를 몰라서 검색해봤다. 만들기는 매우 쉬웠던 것 같다. (youtu.be/_hxFgg7TLZQ?t=193이거 3분 13초 ~ 5분까지 봤음.) BFS는 깊이를 기준으로 깊이가 1인 노드 탐색 -> 2인 노드 탐색 -> 3인 노드 탐색... 으로 진행되는데, 여기서 깊이(자식) = 체스말의 이동 횟수라고 생각하면 금방 해결할 수 있는 문제였다.

탐색 순서는 사실 한번 이동해서 갈 수 있는곳 -> 두번 이동해서 갈 수 있는곳 -> 세번 이동해서 갈 수 있는... 이런식으로 상당히 비효율적으로 진행되는 것 같다.

 

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
bool QueCheck[300][300] = { false, };
 
struct int3
{
    int x;
    int y;
    int Count;
};
 
void Knight(int MapSize, int StartX, int StartY, int EndX, int EndY)
{
    int Move1[8] = {1, 1, 2, 2, -1, -1, -2, -2 };
    int Move2[8] = {2, -2, 1, -1, -2, 2, -1, 1 };
    int Count = 0;
    memset(QueCheck, false, sizeof(QueCheck));
    queue<int3> Que;
    Que.push({ StartX, StartY, 0 });
    while (true)
    {
        if (Que.front().x == EndX && Que.front().y == EndY)
        {
            cout << Que.front().Count << endl;
            return;
        }
 
        for (int i = 0; i < 8; ++i)
        {
            if (Que.front().x + Move1[i] < 0 || Que.front().x + Move1[i] > MapSize-1 || Que.front().y + Move2[i] < 0 || Que.front().y + Move2[i] > MapSize-1)
                continue;
            if (!QueCheck[Que.front().x + Move1[i]][Que.front().y + Move2[i]])
            {
                QueCheck[Que.front().x + Move1[i]][Que.front().y + Move2[i]] = true;
                Que.push({ Que.front().x + Move1[i], Que.front().y + Move2[i], Que.front().Count +1});
            }
        }
        Que.pop();
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int Num;
    cin >> Num;
    for (int i = 0; i < Num; ++i)
    {
        int a, s, d, f, g;
        cin >> a >> s >> d >> f >> g;
        Knight(a,s,d,f,g);
    }
}