백준(BOJ) 그래프순회(BFS) 나이트의 이동 (7562) - Silver 1

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

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

문제 해결

전형적인 BFS 최단경로 탐색알고리즘을 이용한 문제이다. 이전에도 많이 풀어봤던 유형이며 차이점은 나이트의 이동범위에 맞게 이동해야 한다는 점이다. 해당 부분만 주의하여 bfs알고리즘을 돌리면 손쉽게 해결이 가능한 문제이다.

 

전체코드

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

using namespace std;

typedef long long ll;
typedef struct point{
    ll x;
    ll y;
}point;

ll dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
ll dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

bool indexCheck(ll size, point p){
    if(p.x < 0 || p.x >= size) 
        return false;
    if(p.y <0 || p.y >= size)
        return false;
    return true;
}
bool distanceCheck(vector<vector<ll> >&distance, point p){
    if(distance[p.y][p.x] != -1)
        return false;
    return true;
}

void bfs(vector<vector<ll> >&distance, queue<point>& q, point end)
{
    while(!q.empty()){
        point old_point, new_point;
        old_point = q.front();
        q.pop();

        for(ll i=0; i<8; i++){
            new_point.x = dx[i] + old_point.x;
            new_point.y = dy[i] + old_point.y;
            if(indexCheck(distance.size(), new_point) == true and distanceCheck(distance, new_point) == true){
                distance[new_point.y][new_point.x] = distance[old_point.y][old_point.x] + 1;
                q.push(new_point);
            }
        }
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll testCase = 0;
    ll size;
    cin >> testCase;

    while(testCase--){
        cin >> size;
        vector<vector<ll> >distance(size, vector<ll>(size, -1));
        point start, end;
        queue<point>q;
        cin >> start.y >> start.x;
        cin >> end.y >> end.x;
        distance[start.y][start.x] = 0;
        q.push(start);
        bfs(distance, q, end);
        cout << distance[end.y][end.x] << "\n";
    }

    return 0;
}