[BOJ S2][C++] 백준 7562번: 나이트의 이동

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

7562번: 나이트의 이동

 

문제

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

입력

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

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

출력

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

 

풀이

BFS 이용해서 간단하게 풀이 가능하다.

단 나이트의 이동방향에 맞게 dx dy 배열들을 설정해주고

이차원 배열은 거리만 담아도 충분하다.

약간의 변형이 가해진 BFS 문제

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

int dis[302][302];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        queue<pair<int, int>> q;
        int n, a, b;
        
        cin >> n;  // 칸 설정
        
        // 초기화
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                dis[i][j] = -1;
            }
        }
        
        cin >> a >> b;  // 출발지 설정
        dis[a][b] = 0;
        q.push({a,b});
    
        cin >> a >> b;  // 도착지 설정
        
        while(!q.empty()){
            pair<int, int> current = q.front();
            q.pop();
            
            for(int dir=0; dir<8; dir++){
                int x = current.first + dx[dir];
                int y = current.second + dy[dir];
                
                if(x<0 || x>=n || y<0 || y>=n) continue;
                if(dis[x][y] >= 0) continue;
                dis[x][y] = dis[current.first][current.second] + 1;
                q.push({x,y});
            }
        }
        
        cout << dis[a][b] << "\n";
    }
    return 0;
}

/*
 */