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

백준의 나이트의 이동(7562) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 체스판의 한 변의 길이와, 나이트의 시작점과 도착점이 주어진다.

- 나이트는 총 8방향으로 움직일 수 있으며(문제참고) 가장 최소횟수로 움직여서 도착점에 도착했을 때, 움직인 횟수를

  구하는 문제이다.

[ 문제풀이 ]

1) 가장 기본적인 BFS / DFS 문제이다. 이 문제에서 조금 다른점이라는 말할 수 있는 부분은 일반적인 문제를 풀 때 방향이

   상하좌우 4방향으로 움직이는 식의 풀이지만, 이 문제에서는 이 방향만 움직일 수 있는 8가지 방향으로 설정해 주면 된다.

   즉, dx[], dy[]의 값만 바꿔주면 된다.

2) 시작점과 도착점의 위치를 기억해 두었다가, BFS/DFS를 구현할 때, 시작점부터 구현하면 되고, 한번 움직일 때 마다 횟수

   를 Count해줄 수 있는 변수만 잘 관리해 주면 된다. 도착점에 도착하게 되면, 그대로 Count한 횟수를 출력시키고 종료시키

   면 된다.

   - 도착점에 도착하게 되도 다른 방법으로 더 빨리 올 수 있는 방법이 있지 않을까 ?

      - BFS / DFS의 동작원리를 조금만 파악한다면, 가장 먼저 도착점에 도착하는 횟수가 최소 횟수라는 것을 알 것이다.

        갈 수 있는 모든 방향으로 가보기 때문에 도착점에 도착하게 되면 그 순간이 가장 최소 횟수가 되는 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 300
using namespace std;
 
int l;
bool Visit[MAX][MAX];
 
int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
 
pair<int, int> Start, End;
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> l;
    cin >> Start.first >> Start.second;
    cin >> End.first >> End.second;
}
 
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 == End.first && y == End.second)
        {
            cout << Cnt << endl;
            return;
        }
 
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && ny >= 0 && nx < l && ny < l)
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
}
 
void Solution()
{
    BFS(Start.first, Start.second);
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}