1 문제

이동 조건이 체스판의 나이트인 BFS를 이용한 최단 경로 문제

2 Idea

BFS를 이용한 최단 거리

3 Code

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

#include <iostream>
#include <vector>
#include <queue>

typedef struct{
    int x;
    int y;
    int time;
} pos;

const std::vector<std::vector<int>> DIRECTION = {
    {1, 2}, {2, 1},
    {1, -2}, {2, -1},
    {-1, 2}, {-2, 1},
    {-1, -2}, {-2, -1}
};

int CalculateNight(const int l, const int x_start, const int y_start, const int x_dst, const int y_dst){
    //check case of 0
    if ((x_start == x_dst) && (y_start == y_dst)){
        return 0;
    }

    int answer = -1;

    std::vector<std::vector<bool>> visit(l, std::vector<bool>(l, false));
    visit[x_start][y_start] = true;

    //make queue
    std::queue<pos> q;
    q.push({x_start, y_start, 0});

    while(!q.empty()){
        const pos current = q.front();
        q.pop();
        
        for (const auto& dir : DIRECTION){
            const int x_next = current.x+dir[0];
            const int y_next = current.y+dir[1];

            if ((x_next == x_dst) && (y_next == y_dst)){
                return current.time+1;
            }

            if ((x_next >= l) || (y_next >= l) || (x_next < 0) || (y_next < 0)){
                //out of map

                continue;
            }
            else if (visit[x_next][y_next]){
                //visit already

                continue;
            }
            else{
                visit[x_next][y_next] = true;
                q.push({x_next, y_next, current.time+1});
            }
        }
    }

    return answer;
}

int main(){
    int T = 0;
    std::cin >> T;

    for (int i=0; i<T; ++i){
        int l = 0;
        std::cin >> l;

        int x_start = 0;
        int y_start = 0;
        std::cin >> x_start >> y_start;

        int x_dst = 0;
        int y_dst = 0;
        std::cin >> x_dst >> y_dst;

        std::cout << CalculateNight(l, x_start, y_start, x_dst, y_dst) << std::endl;
    }

    return 0;
}