백준 12851 숨박꼭질2 C++ [컴공과고씨]

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

12851번: 숨바꼭질 2

 

문제를 읽어보면 탐색 문제인 것을 알 수 있습니다.

BFS를 사용해서 풀었습니다.

 

전체적인 문제 해결 방법은 수빈이의 위치와 동생의 위치를 확인 후 같지 않다면 수빈이의 위치를 이동시킨 후 큐에 넣어줍니다.  큐가 빌 때까지 반복 해 주면 됩니다.

그러다 처음으로 위치가 같아지면 이제까지 걸린 시간을 저장해줍니다. 그 후 위치가 같고 그 전에 저장해둔 걸린 시간과 같은 방식을 찾는다면 카운트를 해주면 됩니다. 

한번 방문한 위치는 체크를 해주어서 중복으로 들어가는 것을 막아야 합니다. 

예를 들어 3이라는 위치를 방문하는데 처음엔 2초 걸린 애가 왔었고 그 다음 4초 걸린 방식으로 왔다면 4초 걸린 방식은 필요가 없기 때문입니다.

 

여기서 주의해야 할 것은 이미 간 위치를 체크 할 때 큐를 넣을 때 체크하는 것이 아니라 pop을 한 후에 체크를 해주는 것이 중요합니다. 

 

이유는 1 4가 입력이 되었다고 하면 

1+1 -> 2*2

1*2 -> 2*2

이렇게 2가지 방법이 있는데 방문 위치를 체크를 push 할 때 하게 되면 1+1 = 2, 1*2= 2 이기 때문에 

2가 이미 방문한 것으로 체크가 되어서 1*2 스킵하게 됩니다. 그래서 1+1과 1*2를 푸시를 한 후에

큐에서 꺼낸 후 2를 방문자 체크를 해주어야 다른 방식으로 같은 결과가 나온 것도 개수에 포함 할 수 있습니다.

 

전체코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, k;
bool first = true; // 처음으로 위치가 같은지
int visit[100003] = { 0 };
int result = 100003;
int result2 = 0;
void bfs(int a, int b){
    queue<pair<int, int>> q;
    q.push(make_pair(a,b)); // a: 수빈위치 b: 시간
    visit[a] = true; // 수빈위치 방문 처리
 
    while(!q.empty()){ // 큐가 빌 때까지
        int x = q.front().first; 
        int cnt = q.front().second;
        q.pop();
 
        visit[x] = true; // pop 후 방문 처리 
        if(!first && result == cnt && x == k){
            // 첫 방식과 다른 방식으로 도달한 방법
            // 위치가 같고, 걸린 시간도 같은지
            result2++; // 카운트
        }
        if(first && x == k){ //처음으로 위치가 동생하고 같을 때
            result = cnt; // 최소 시간 저장
            first = false; // 처음 방문 여부 false로
            result2++; // 카운트
        }
 
        if(x+1 < 100001 && x+1 >= 0 && !visit[x+1]){
            // 걷기 +1
            // 범위 체크 후 다음 점이 방문 된 점인지 확인
            q.push(make_pair(x + 1, cnt + 1)); 
        }
        if(x-1 < 100001 && x-1 >= 0 && !visit[x-1]){
            // 걷기 -1
            q.push(make_pair(x - 1, cnt + 1));
        }
        if(x*2 < 100001 && x*2 >= 0 && !visit[x*2]){
            // 순간이동 *2
            q.push(make_pair(x * 2, cnt + 1));
        }
    }
}
int main(){
    cin >> n >> k;
 
    bfs(n, 0);
    cout << result << endl; // 걸리는 최소 시간
    cout << result2 << endl; // 방법 개수
    return 0;
}

체감 난이도	걸린 시간	후기	참고	사용 알고리즘
중	1h	반례를 생각 못해서 시간이 오래 걸렸음.	반례 참고	BFS (Breadth First Search)