Boj

[Boj] 백준 C++ #16948 데스 나이트

ima9ine4 2025. 1. 7. 14:18
728x90

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

 

📍 알고리즘 분류 : BFS

 

📍 문제 풀이

이 문제는 큐를 이용해서 BFS로 해결할 수 있다. (r,c)의 위치에서 이동할 수 있는 칸은 아래 그림과 같이 총 6개이다.

 

따라서 한 위치에 대해 이동할 수 있는 6개의 위치를 모두 탐색해주면 된다.

체스판을 넘어가거나, 이미 방문한 위치가 아니면 큐에 넣어준다.

이미 방문했다면, 지금 방문한 것은 최단 횟수의 방문이 아니라는 것이므로 고려해줄 필요가 없다. 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이다.

 

위 과정을 큐가 빌 때까지, 혹은 목표 지점에 도달할 때까지 반복한다.

 

이 문제의 핵심 로직은 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이라는 것이다. 따라서 가장 먼저 목표 지점에 도달했을 때가 최소 이동 횟수이다. 그 이유는 BFS 탐색이기 때문이다. 한 번 이동을 했을 때 방문 가능한 지점들을 모두 탐색하고, 그리고 나서 두 번 이동했을 때 방문 가능한 지점들을 모두 탐색한다. 따라서 처음 방문 시 그게 최단 경로이다!

 

 

📍 소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
queue<pair<int,int>> q;
vector<vector<int>> map;
vector<vector<int>> visited;

void move(int x, int y, int a, int b){
    // 체스판을 벗어났거나 이미 방문한 곳이라면
    if( x+a < 0 || x+a > n-1 || y+b <0 || y+b > n-1 || visited[x+a][y+b] == 1){
        return;
    }else{
        // 방문했음을 기록, 다음 위치를 q에 넣고, 방문 횟수 업데이트
        visited[x+a][y+b] = 1;
        q.push({x+a,y+b});
        map[x+a][y+b] = map[x][y] + 1;
    }
}

int main(){
    cin>>n;
    map.resize(n,vector<int> (n,0));
    visited.resize(n,vector<int>(n,0));
    int x_start, y_start, x_end, y_end;
    cin>>x_start>>y_start>>x_end>>y_end;

    q.push({x_start,y_start});
    map[x_start][y_start] = 0;
    int cantmove = 1;

    vector<pair<int,int>> direction = {{-2,-1}, {-2,1}, {0,-2}, {0,2}, {2,-1}, {2,1}};
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if( x == x_end && y == y_end){
            cout<<map[x][y]<<endl;
            cantmove = 0;
            break;
        }
        for(int i=0;i<6;i++){
            move(x, y, direction[i].first, direction[i].second);
        }
    }
    // 이동할 수 없는 경우
    if(cantmove){
        cout<<-1<<endl;
    }
}

 

 

📍 유사 문항

백준 #16928 뱀과 사다리 게임

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

 

 

와아.. 드디어 혼자 힘으로 BFS 문제를 풀었다! 그것도 딱 30분만에!
코드 작성할 거 다 작성하고 딱 실행시켜보았는데 생각한대로 다 돌아가서 너무 뿌듯했다 :)))))
얼마전 BFS문제를 풀 때는 너무 어려웠는데, 그때 풀었던 문제와 비슷한 유형이라서 풀 수 있었던 것 같다. 

 

728x90
반응형

'Boj' 카테고리의 다른 글

[Boj] 백준 C++ #2138 전구와 스위치  (2) 2025.01.05
[Boj] C++ #1339 단어 수학  (2) 2025.01.04
[Boj] 백준 C++ #1202 보석 도둑  (0) 2024.12.27
[Boj] 백준 C++ #1914 하노이탑  (0) 2024.09.20
[Boj] 백준 C++ #11726 2xn 타일링  (0) 2024.08.11