백준 숨바꼭질4 C++

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

13913번: 숨바꼭질 4

---

BFS를 했을 떄, 최단 거리를 역추적하는 문제입니다.

먼저 주어진 n과 k를 입력받고,

최단거리 저장 배열 dt를 만들고 큰 값으로 초기화를 해주었습니다.

void input(){
    cin >> n >> k;
    for(int i = 0;i<=MAX;i++){
        dt[i] = 987654321;
    }
}

 

요기서 MAX는 최대 입력이 100,000이기때문에 100,000으로 초기화를 해주었고

방문한 칸이 100,000을 넘어가는지, 0미만인지 확인하는 함수도 만들어 두었습니다.

bool isValid(int node){
    if(node > MAX || node < 0){
        return false;
    }
    return true;
}

이제 BFS함수를 정의해줍니다.

void bfs(int start){
    queue<pair<int,int>> q;
    dt[start] = 0;
    q.push({dt[start],start});
 
    while(!q.empty()){
        int width = q.front().first;
        int node = q.front().second;
        q.pop();
        if(node == k){
            break;
        }
        if(isValid(node + 1) && width + 1 < dt[node + 1]){
            dt[node+1] = width + 1;
            q.push({dt[node+1],node+1});
        }
        if(isValid(node - 1) && width + 1 < dt[node - 1]){
            dt[node-1] = width + 1;
            q.push({dt[node-1],node-1});
        }
        if(isValid(node * 2) && width + 1 < dt[node *2]){
            dt[node*2] = width + 1;
            q.push({dt[node*2],node*2});
        }
    }
 
}

BFS를 돌고나면, 거리 테이블이 갱신됩니다.

다시 K부터 N까지 가면서, 현재 큐의 Front의 거리테이블 - 1인 것들만 골라줍니다.

(큐는 pair<int,int>타입, 첫번쨰에 거리테이블 값을, 두번쨰에 위치 저장)

 

vector<pair<int,int>> findAlldistance(int k){
    vector<pair<int,int>> ans;
    queue<pair<int,int>> q;
    q.push({dt[k],k});
    ans.push_back({dt[k],k});
 
    while(!q.empty()){
        int width = q.front().first;
        int node = q.front().second;
        q.pop();
        if(node == n){
            break;
        }
 
        if(isValid(node-1) && dt[node-1] == width - 1){
            q.push({dt[node-1],node-1});
            ans.push_back({dt[node-1],node-1});
        }
        if(isValid(node+1) && dt[node+1] == width - 1){
            q.push({dt[node+1],node+1});
            ans.push_back({dt[node+1],node+1});
        }
        if(isValid(node/2) && dt[node/2] == width - 1){
            q.push({dt[node/2],node/2});
            ans.push_back({dt[node/2],node/2});
        }
 
    }
    return ans;
}

 

 

전체 소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 100000
using namespace std;
 
int n,k;
 
int dt[MAX + 1];
void input(){
    cin >> n >> k;
    for(int i = 0;i<=MAX;i++){
        dt[i] = 987654321;
    }
}
 
bool isValid(int node){
    if(node > MAX || node < 0){
        return false;
    }
    return true;
}
 
void bfs(int start){
    queue<pair<int,int>> q;
    dt[start] = 0;
    q.push({dt[start],start});
 
    while(!q.empty()){
        int width = q.front().first;
        int node = q.front().second;
        q.pop();
        if(node == k){
            break;
        }
        if(isValid(node + 1) && width + 1 < dt[node + 1]){
            dt[node+1] = width + 1;
            q.push({dt[node+1],node+1});
        }
        if(isValid(node - 1) && width + 1 < dt[node - 1]){
            dt[node-1] = width + 1;
            q.push({dt[node-1],node-1});
        }
        if(isValid(node * 2) && width + 1 < dt[node *2]){
            dt[node*2] = width + 1;
            q.push({dt[node*2],node*2});
        }
    }
 
}
 
bool isConnected(int prevDist,int nextDist){
    if(prevDist + 1 == nextDist){
        return true;
    }
 
    if(prevDist - 1 == nextDist){
        return true;
    }
 
    if(prevDist * 2 == nextDist){
        return true;
    }
 
    return false;
}
 
vector<pair<int,int>> findAlldistance(int k){
    vector<pair<int,int>> ans;
    queue<pair<int,int>> q;
    q.push({dt[k],k});
    ans.push_back({dt[k],k});
 
    while(!q.empty()){
        int width = q.front().first;
        int node = q.front().second;
        q.pop();
        if(node == n){
            break;
        }
 
        if(isValid(node-1) && dt[node-1] == width - 1){
            q.push({dt[node-1],node-1});
            ans.push_back({dt[node-1],node-1});
        }
        if(isValid(node+1) && dt[node+1] == width - 1){
            q.push({dt[node+1],node+1});
            ans.push_back({dt[node+1],node+1});
        }
        if(isValid(node/2) && dt[node/2] == width - 1){
            q.push({dt[node/2],node/2});
            ans.push_back({dt[node/2],node/2});
        }
 
    }
    return ans;
}
 
int main(void){
    input();
    bfs(n);
    vector<pair<int,int>> Answer = findAlldistance(k);
    int startWidth = dt[k];
    int startNode = k;
    vector<int> reversed_Answer;
    cout << dt[k] << '\n';

    reversed_Answer.push_back(startNode);
    for(int i = 0;i<Answer.size();i++){
        if(Answer[i].first == startWidth - 1 && isConnected(Answer[i].second,startNode)){
            reversed_Answer.push_back(Answer[i].second);
            startWidth = Answer[i].first;
            startNode = Answer[i].second;
           
        }
    }

    reverse(reversed_Answer.begin(),reversed_Answer.end());
    for(int i = 0;i<reversed_Answer.size();i++){
        cout << reversed_Answer[i] << ' ';
    }
 
}