[백준 7562 - C++] 나이트의 이동 : BFS

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제

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

입력

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

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

 

출력

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

 

 

풀이

BFS알고리즘을 이용하여 풀이하였다.

나이트는 8가지 방향으로 이동할 수 있으므로 적어둔 이동방향 벡터를 모두 고려해야한다.

출발점 부터 큐에 넣고 8가지 이동방향에 대해 탐색하면서 도착점에 도달하는지를 확인하면 된다.

또한 출발점과 도착점이 같은 경우엔 이동할 필요가 없으므로 처음에 미리 체크해둔다.

가장 중요한 것은 테스트케이스가 하나가 아니므로 큐와 visited 배열을 초기화 해주어야 한다는 것이다!!

 

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int X[8] = {1, 2, -1, 1, -1, -2, 2, -2};
int Y[8] = {2, 1, 2, -2, -2, -1, -1, 1};
int visited[301][301];

queue<pair<pair<int, int>,int>> check;

int main(void){
    int tc;
    int n;
    int s_x, s_y;
    int f_x, f_y;
    int x, y;
    int n_x, n_y;
    int cnt;
    int result;
    
    scanf("%d", &tc);
    
    for(int i=0; i<tc; i++){
        scanf("%d", &n);
        scanf("%d %d", &s_x, &s_y);
        scanf("%d %d", &f_x, &f_y);
        
        if(s_x == f_x && s_y == f_y){
            printf("0\n");
            continue;
        }
        
        check.push(make_pair(make_pair(s_x, s_y), 0));
        visited[s_x][s_y] = 1;
        
        while(!check.empty()){
            x = check.front().first.first;
            y = check.front().first.second;
            cnt = check.front().second;
            if(x == f_x && y == f_y){
                result = cnt;
                break;
            }
            check.pop();
            
            for(int i=0; i<8; i++){
                n_x = x+X[i];
                n_y = y+Y[i];
                if(n_x <0 || n_x >=n || n_y<0 || n_y >=n)
                    continue;
                if(visited[n_x][n_y] == 1)
                    continue;
                check.push(make_pair(make_pair(n_x, n_y), cnt+1));
                visited[n_x][n_y] = 1;
            }
        }
        while(!check.empty())
            check.pop();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                visited[i][j] = 0;
            }
        }
        printf("%d\n", result);
    }
}