[백준/C++] 7562번 : 나이트의 이동 풀이

문제 7562 번 : 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제

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

 

입력

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

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

 

출력

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

 

 

오랜만에 풀어보는 BFS 문제이다.

나이트의 이동 경로에 따른 dy, dx 값만 제대로 넣어준다면 큰 무리 없이 풀 수 있는 무난한 문제이다.

 

 

풀이

#include <iostream>
#include <queue>

using namespace std;

int n, x1, y1, x2, y2;

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

void bfs(){
    int visited[301][301] = {false,};
    queue <pair<int,pair<int,int>>> que;
    
    que.push(make_pair(0, make_pair(y1, x1)));
    visited[y1][x1] = true;
    
    while(!que.empty()){
        int cnt = que.front().first;
        
        auto now = que.front().second;
        int y = now.first;
        int x = now.second;
        
        que.pop();
        
        if(y==y2 && x==x2) {
            cout << cnt << endl;
            break;
        }
        
        for(int i=0; i<8; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny<0|| nx<0|| ny>=n || nx>=n) continue;
            if(visited[ny][nx]) continue;
            
            visited[ny][nx] = true;
            que.push(make_pair(cnt+1, make_pair(ny, nx)));
        }
    }
}

int main(void){
    
    int t;
    cin >> t;
    for(int i=0; i<t; i++){
        cin>>n;
        cin >> x1 >> y1;
        cin >> x2 >> y2;
        bfs();
    }
    
    return 0;
}

 

 

풀이 인증