[C++] 백준 13549 : 숨바꼭질3

문제

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

 

 

 

풀이

나의 경우 BFS로 풀었다.

방문하지 않은 위치에 대해 범위를 체크해주면서 큐에 다음 위치를 넣어준다.

이때 큐에 넣는 순서가 중요하다. (<- 그래서 일반적인 BFS라고는 볼 수 없다. 정확히는 0-1 BFS 라고 한다.)

1. 순간이동

2. 좌/우 걷기

 

그리고 가장 먼저 도착했을 때의 시간을 출력해주면 된다.

 

코드

#include <iostream>
#include <queue>
#include <set>
using namespace std;

struct State{
    int position, c_t;
};
int n,k, min_time;
set<int> s;

void bfs(){
    queue<State> q;
    
    // 시작점을 큐에 삽입
    q.push({n,0});
    
    //bfs
    while(!q.empty()){
        
        State cur = q.front();
        q.pop();
        
        // 이미 방문한 곳이라면
        if(s.find(cur.position) != s.end()){
            continue;
        }
        s.insert(cur.position);
        
        // 더 이상 진행할 필요가 없다면(시간이 길어졌다면)
        if(cur.c_t >= min_time && min_time !=0) continue;
        
        // 현 위치가 범위를 벗어난 경우
        if(cur.position > (k+n)+1 || cur.position <0) continue;
        
        // 동생을 찾았다면
        if (cur.position == k) {
            min_time = cur.c_t;
            return; // 가장 먼저 도달한 것이 최소 시간
        }
        
        // 동생을 찾지 못했다면
        else{
            if(cur.position*2 <= 100000){
                q.push({cur.position*2, cur.c_t}); // 순간이동
            }
            if (cur.position - 1 >= 0) {
            q.push({cur.position - 1, cur.c_t + 1}); // 왼쪽 걷기
            } 
            if (cur.position + 1 <= 100000) {
            q.push({cur.position + 1, cur.c_t + 1}); // 오른쪽 걷기
            }   
        }
    }
}

int main()
{   
    cin >> n >> k;
    bfs();
    cout << min_time << "\n";
    return 0;
}

 

 

메모

처음 이 문제를 보았을 때, "최소 시간" 이라는 표현을 보고 BFS로 풀어야지! 라고 생각하고 접근했다.
그래서 일반적인 BFS에서는 큐에 원소를 넣는 순서가 중요하지 않으니 그냥 넣어서 풀었다. 하지만 이렇게 구현했을 때에는 통과되지 않았고 단지 큐에 삽입하는 순서만 바꾸었더니 통과되었다.

사실 이 문제에서는 순간이동을 할 때는 비용이 증가되지 않지만, 걷기를 선택할 경우 비용이 증가된다.
따라서 가중치가 다르다. 이 경우 일반적인 BFS로 풀 수는 없다는 점을 간과했다. (가중치를 고려해야 한다는 점을..!)

 

BFS : 가중치가 모두 동일한 경우. 큐에 원소 삽입 순서 중요하지 않음.
0-1 BFS : 가중치가 0 또는 1인 경우. 덱을 사용하여 가중치 0인 경로를 먼저 탐색.