[백준알고] [1697]:숨바꼭질

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

숨바꼭질 문제입니다...

DFS로 풀어보려 했으나 도저히 못풀겠어서 BFS 방식으로 푼 문제입니다 ^_^

포스팅 시작합니다~~

숨바꼭질 성공 풀이

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	27320	7524	4749	24.980%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 

5 17

예제 출력 

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

문제는 이렇습니다....

수빈이의 위치를 입력받고 동생의 위치를 입력받아서 동생의 위치까지 가는데 시간이 얼마나 걸리느냐...그런문제입니다.

수빈이의 위치 N에서 N+1 또는 N-1 또는 N*2 만큼 이동하는경우 시간이 1초씩 추가되고.. 만나는 동생을 만났을때 결과적으로 몇초가 걸렸는지 확인하는거죠!

위의 Test Case에서 5 17을 입력받았고, 5에서 -1또는 +1또는 *2 연산을 계속적으로 해서 언제 17이라는 수가 나올까를 구하는건데....

처음에는 5라는 수를 입력받고 17까지 손으로 구해보려고 5*2*2-1-1-1 뭐 이런식으로 어느정도면 최단시간에 갈수있겠다 해봤는데 결국에는 5*2-1*2-1 이라는.... 생각해보지도 못한 연산이 나와서 어떻게 구현할까 하다가 BFS로 큐에다가 다음 3개의 연산 결과값을 계속적으로 추가해서 큐의 front값이 동생의 위치가 되면 빠져나오는 방식으로 설계를 했습니다!

아래는 전체 소스코드입니다.

#include<iostream>
#include<queue>
using namespace std;
#define MAX_VALUE 100001 //인덱스 100000까지 :: +1까지 넣음
bool visit[MAX_VALUE];
int N, M;        //N    수빈이위치, M 동생위치
 
int bfs(int n, int m) {
    int time = 0;        //몇초만에 찾았는지 ?
    queue<int> q;
    q.push(n);
 
    while(1) {
        int size = q.size();
 
        for(int i=0; i<size; i++) {
            n = q.front();
            q.pop();
            if(n == m)
                return time;        
            if(n > 0 && visit[n-1] == 0) {
                q.push(n-1);
                visit[n-1] = 1;
            }
            if(n < 100000 && visit[n+1] == 0) {
                q.push(n+1);
                visit[n+1] = 1;
            }
            if(n*2 <= 100000 && visit[n*2] == 0) {
                q.push(n*2);    
                visit[n*2] = 1;
            }
        }
        time++;
    }
}
 
int main() {
    cin >> N >> M;
    cout << bfs(N, M);
    return 0;
}

메인함수 설명은 그냥 bfs에 수빈이위치와 동생의위치를 넣는것이므로 생략하겠습니다.

int bfs(int n, int m) {
    int time = 0;        //몇초만에 찾았는지 ?
    queue<int> q;
    q.push(n);
 
    while(1) {
        int size = q.size();
 
        for(int i=0; i<size; i++) {
            n = q.front();
            q.pop();
            if(n == m)
                return time;        
            if(n > 0 && visit[n-1] == 0) {
                q.push(n-1);
                visit[n-1] = 1;
            }
            if(n < 100000 && visit[n+1] == 0) {
                q.push(n+1);
                visit[n+1] = 1;
            }
            if(n*2 <= 100000 && visit[n*2] == 0) {
                q.push(n*2);    
                visit[n*2] = 1;
            }
        }
        time++;
    }
}

bfs함수 코드입니다. n으로 수빈이위치, m으로 동생위치가 매개변수로 들어오게 됩니다.

Queue를 사용해서 수빈이의 첫 위치에서 +1, -1, *2한 결과값을 계속적으로 Queue에 쌓게 됩니다.

Queue의 크기만큼 for문을 반복해야하는 이유는 (-1, +1, *2)를 현재 큐에 들어있는 수가 모두 해주고 다시 Queue에 넣어야 되기 때문이죠.

if(n==m) 이부분은 큐를 계속적으로 push pop 하는중에 front의 값이 동생의 위치이면 함수를 return시키고, time 값을 반환합니다.

time값이 증가하는 순간은 queue에 있던 값들이 모두 (-1, +1, *2) 연산을 하고, 다시 큐에다가 쌓은 뒤 pop된 후 입니다.

여기서, 저는 처음에 visit 배열을 조건문에 넣지 않아서, 메모리 초과가 나왔었는데요..

visit배열을 통해서 bfs를 통해 한번 방문했던 위치는 다시 방문하지 않아도 됩니다!

수빈이 위치를 1로두고, 동생의 위치를 1000으로 두면 대략 5초정도 걸리더군요 ㅡ.ㅡ .....

그래서 다음 큐에 넣을 숫자를 visit배열을 통해서 1로만들어주고, 그걸 조건식에 적용함으로써 방문했던곳은 다시 큐에 집어넣지 않게되는거죠!

DFS로 했을땐 .... 너무나 복잡해서 BFS로 했더니 쉽게 풀렸던 문제였습니다 ^0^~