[BFS] 7562번 나이트의 이동

7562번 나이트의 이동

 

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

 

문제

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

 

입력

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

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

 

출력

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

 

예제 입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

 

예제 출력

5
28
0

 

해결방법

정말 간단한 BFS 탐색 문제이다

나이트는 8개의 방향으로 이동이 가능한데 dist 배열을 통해 원하는 목표의 dist 를 출력해주면 되는 문제이다

 

사실 N-Queen, 비숍 문제를 풀고나서 이 문제를 봤기 때문에 난이도가 있을 줄 알았는데...흠....

시간이 남아서 눈에 보이는 문제 아무거나 풀었는데 이제는 난이도를 보고 선택을 해야겠다...!!

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 301
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int testcase;
int n;
node s,e;
int dist[MAX][MAX];
bool visited[MAX][MAX];

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

void bfs(){
    queue<node> q;
    q.push(s);
    dist[s.first][s.second] = 0;
    visited[s.first][s.second] = true;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x==e.first && y==e.second){
            cout << dist[x][y] << "\n";
            return;
        }
        
        for(int i=0; i<8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
            
            if(!visited[nx][ny]){
                q.push(node(nx,ny));
                dist[nx][ny] = dist[x][y] + 1;
                visited[nx][ny] = true;
            }
        }
    }
    cout << 0 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    
    for(int t=0; t<testcase; t++){
        cin >> n;
        
        memset(dist, -1, sizeof(dist));
        memset(visited, false, sizeof(visited));
        
        cin >> s.first >> s.second;
        cin >> e.first >> e.second;
        
        bfs();
    }
}