7562: 나이트의 이동

• toc {:toc}

문제

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

입력

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

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

출력

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

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

풀이

2022-08-07

BFS를 이용하여 문제를 풀이하지만 위치가 다르기 때문에 변화하는 dx, dy값을 다르게 설정해주면 어려움 없이 풀이 할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
int dist[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 l;
pair<int, int> now, target;
queue<pair<int, int>> q;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        cin >> l;
        cin >> now.X >> now.Y;
        cin >> target.X >> target.Y;
 
        while(!q.empty()){
            q.pop();
        }
 
        // dist ĂĘąâČ­
        for(int i = 0; i < l; i++){
            for(int j = 0; j < l; j++){
                dist[i][j] = -1;
            }
        }
        q.push({now.X, now.Y});
        dist[now.X][now.Y] = 0;
        if(now.X == target.X && now.Y == target.Y){
            cout << dist[now.X][now.Y] << endl;
            continue;
        }
 
        for(int i = 0; i < l; i++){
            for(int j = 0; j < l; j++){
                while(!q.empty()){
                    auto cur = q.front(); q.pop();
                    for(int dir = 0; dir < 8; dir++){
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if(nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
                        if(dist[nx][ny] >= 0) continue;
                        dist[nx][ny] = dist[cur.X][cur.Y] + 1;
                        if(target.X == nx && target.Y == ny){
                            cout << dist[nx][ny] << endl;
                            break;
                        }
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
}

2023-09-07 풀이

BFS 문제인 것을 알면 구조는 정형화되어 있어 풀이가 변하지 않는 것 같다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
int dx[8] = {-1, -1, 1, 1, -2, -2, 2, 2};
int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1};
int T, I;
queue<pair<int, int>> q;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    pair<int, int> start, end;
 
    cin >> T;
 
    
    while(T--){
        int board[303][303] = {0,};
        int dist[303][303] = {0,};
        cin >> I;
        cin >> start.X >> start.Y;
        q.push(start);
        cin >> end.X >> end.Y;
        
 
        if (start.X == end.X && start.Y == end.Y) {
            cout << 0 << '\n';
            continue;
        }
        while(!q.empty()){
            auto cur = q.front(); q.pop();
            for(int dir = 0; dir < 8; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx < 0 || nx >= I || ny < 0 || ny >= I) continue;
                if(dist[nx][ny] > 0) continue;
                dist[nx][ny] = dist[cur.X][cur.Y]+1;
                if(nx == end.X && ny == end.Y){
                    cout << dist[nx][ny] << '\n';
                    break;
                }
                q.push({nx, ny});
            }
        }
        
    }
 
    return 0;
}