[백준/c++] 18404번: 현명한 나이트

 

 

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

18404번: 현명한 나이트

 

문제 요약

 

NxN 체스판의 특정 위치에 하나의 나이트

M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수 계산하는 프로그램

 

[이동 방법]

현재 나이트 위치 (X, Y)

(X-2, Y-1), (X-2, Y+1), (X-1, Y-2), (X-1, Y+2), (X+1, Y-2), (X+1, Y+2), (X+2, Y-1), (X+2, Y+1)

 

모든 말들의 위치는 중복 X, 나이트가 도달할 수 있는 위치로만 주어진다.

 

 

범위

 

체스판 크기 N, 말 개수 M(1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000)

나이트 위치 X, Y (1 ≤ X, Y ≤ N) 

말 위치 A, B (1 ≤ A, B ≤ N)

 

 

---

 

 

상대편 말을 잡기 위한 최소 이동 수 = 최단 거리 = BFS

각 말들의 위치(A, B)를 BFS의 시작점으로 넣어주면 된다. 

 

✨ 체스판과 같이 좌표가 찍히는 문제는 꼭 1부터 시작해야 하는지 확인하자.

 

#include <iostream>
#include <queue>
using namespace std;
int n, m, X, Y, dist[502][502];
int dir[8][2] = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}};

void input(){
    cin >> n >> m;
    cin >> X >> Y;
}

void BFS(){
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = -1;
    queue<pair<int, int>> q;
    q.push({X, Y});
    dist[X][Y] = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<8; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 1 || dy < 1 || dx > n || dy > n) continue; //경로이탈 pass
            if(dist[dx][dy] != -1) continue;                   //방문한 곳 pass
            dist[dx][dy] = dist[x][y] + 1;
            q.push({dx, dy});
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    BFS();
    for(int i=0; i<m; i++) {
        int horseX, horseY;
        cin >> horseX >> horseY;
        cout << dist[horseX][horseY] << ' ';
    }
    cout << '\n';
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!