[백준 7562] 나이트의 이동

0. 제목

• 백준 7562 나이트의 이동
• BOJ 7562 나이트의 이동
• C++ 7562 나이트의 이동

---

1. 문제

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

---

2. 풀이

• dfs가 아닌 bfs를 이용한다.
• bfs를 활용했을 때 목적지에 도착했을 당시 최소 이동 횟수이기 때문이다. dfs는 목적지에 도착했을 때 최소 이동 횟수가 아니기 때문이다.
• 최소 이동 횟수를 구할 때는 bfs로 구해야 할 것같다.(내 생각)
• 배열 arr은 출발지로부터 해당 좌표(i, j)까지의 최소 이동 횟수를 담아 놓은 것이다.
• bfs방식으로 큐를 이용하여 출발 좌표부터 탐색을 시작하고 출발지 좌표가 나오면 그 때 arr배열의 값을 출력해주고 탈출하면 된다.
• 테스트케이스도 입력을 받으니 테스트케이스를 하나 실행할때 마다 배열들을 초기화시켜준다.

---

3. 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int arr[301][301];
bool checked[301][301];
 
int dx[8] = {1,2,2,1,-1,-2,-2,-1};
int dy[8] = {2,1,-1,-2,-2,-1,1,2};
 
int I;//체스판의 한 변의 길이
queue<pair<int, int>> q;
int srcX, srcY, dstX, dstY;
 
void bfs(int a, int b){
    q.push(make_pair(a, b));
    checked[a][b] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == dstX && y == dstY){
            cout << arr[x][y] << '\n';
            
            while(!q.empty()){
                q.pop();
            }
            break;
        }
        
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < I && ny >= 0 && ny < I){
                if(checked[nx][ny] == false){
                    checked[nx][ny] = true;
                    arr[nx][ny] = arr[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int main(int argc, const char * argv[]) {
    int T;
    cin >> T;
 
    for(int i = 0; i < T; i++){
        cin >> I;
        cin >> srcX >> srcY >> dstX >> dstY;
        bfs(srcX, srcY);
        memset(arr, 0, sizeof(arr));
        memset(checked, false, sizeof(checked));
    }
    return 0;
}