[ 백준 16948 ] 데스 나이트 (C++)

백준의 데스나이트(16948) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 하나의 시작점에서 도착점까지 갈 때, 최소 이동횟수를 구하는 것이 문제이다.

   본인은 너비우선탐색(BFS) 알고리즘을 이용해서 구현해 보았다. BFS에 대한 기본적인 개념 정도만 있으면 구현에

   헷갈리거나 어려울만한 부분은 없을 것 같은 문제이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 200
using namespace std;
 
int N, R1, R2, C1, C2;
bool Visit[MAX][MAX];
 
int dx[] = { -2, -2, 0, 0, 2, 2 };
int dy[] = { -1, 1, -2, 2, -1, 1 };
 
void Input()
{
    cin >> N;
    cin >> R1 >> C1 >> R2 >> C2;
}
 
void BFS(int a, int b)
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == R2 && y == C2)
        {
            cout << Cnt << endl;
            return;
        }
        
        for (int i = 0; i < 6; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
    cout << -1 << endl;
}
 
void Solution()
{
    BFS(R1, C1);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}