[BFS] 백준 7562번 - 나이트의 이동 (정답률 44%)

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

7562번: 나이트의 이동

BFS 알고리즘 연습 문제이다.

나이트가 갈 수 있는 방향 8개가 주어지고, 현재 위치와 목표로 하는 위치가 주어졌을 때, 몇 번만에 목적지로 이동할 수 있는지 묻는 문제였다. 전형적인 BFS 문제로, 현 위치에서 갈 수 있는 방향으로 가지를 각각 뻗어나가며 정답에 도달하는 경우 종료하는 알고리즘을 사용했다.

 

아래는 BFS 소스코드. (20ms)

 

#include <iostream>
#include <queue>
#define maxlen 300
 
using namespace std;
int l; // 0, 1, ..., l-1
int start_r, start_c, target_r, target_c;
int map[maxlen][maxlen]; // 0 ~ 299.
bool check[maxlen][maxlen];
int answer;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[8] = { { 1, 2 }, { 2, 1 }, { -1, 2 }, { 1, -2 }, { -1, -2 }, { -2, 1 }, { 2, -1 }, { -2, -1 } };
// 나이트가 갈 수 있는 방법 8가지.
 
void reset(){
    for (int i = 0; i < maxlen; i++)
        for (int j = 0; j < maxlen; j++){
            map[i][j] = 0; // 초기화.
            check[i][j] = false; // 초기화
        }
}
 
void bfs(int row, int col, int curtime){
    queue<pair<int, pair<int, int> > > q;
    check[row][col] = true;
    q.push(make_pair(curtime, make_pair(row, col)));
    while (!q.empty()){
        int cur_row = q.front().second.first;
        int cur_col = q.front().second.second;
        int cur_time = q.front().first;
        if (cur_row == target_r && cur_col == target_c){ // 정답 찾음.
            answer = cur_time;
            break;
        }
        q.pop();
        for (int i = 0; i < 8; i++){
            int n_r = cur_row + direction[i].dr;
            int n_c = cur_col + direction[i].dc;
            if (n_r >= 0 && n_r < l && n_c >= 0 && n_c < l)
            {
                if (!check[n_r][n_c]){
                    check[n_r][n_c] = true;
                    q.push(make_pair(cur_time + 1, make_pair(n_r, n_c)));
                }
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int TC;
    cin >> TC;
    for (int i = 0; i < TC; i++){
        reset();
        cin >> l;
        cin >> start_r >> start_c;
        cin >> target_r >> target_c;
        bfs(start_r, start_c, 0);
        cout << answer << '\n';
    }
    return 0;
}