[1697] 숨바꼭질(C++)

문제

1697번: 숨바꼭질

 

 

해결 방법

살짝 까다로웠던 문제.

분명 트리로 푸는건 아닌 것 같은데 자꾸 트리만 생각나고 bfs로 어떻게 풀어야할지 감이 안잡혀서 결국 구글링을 했다.

 

알고리즘은 간단하다.

1. 수빈이의 위치(n), 동생의 위치(k)를 인수로 bfs 함수를 실행

2. 수빈이의 위치(n)와 동생의 위치(k)가 같다면 return 시간

3. 같지 않고 n-1이 0보다 크면서 방문한 적이 없다면 큐에 추가

4. 같지 않고 n+1이 100000보다 작거나 같으면 큐에 추가

5. 같지 않고 2*n이 100000보다 작거나 같으면 큐에 추가

6. 큐 사이즈만큼 다 돌면 time 증가하고 큐 사이즈 업데이트

 

5
size = 1					time = 0

4	6	10
size = 3					time = 1

6	10	3	8
size = 3					time = 1

10	3	8	7	12
size = 3					time = 1

3	8	7	12	9	11	20
size = 7					time = 2

8	7	12	9	11	20	2
size = 7					time = 2

 

위와 같이 진행된다고 보면 된다.

표로 그려서 가독성은 조금 없지만 그림으로 그려보면 트리와 같은 구조이다.

 

 

내 코드(C++)

// [1697] 숨바꼭질
// https://www.acmicpc.net/problem/1697
// BFS

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

int visited[100001] = { 0, };
int bfs(int x, int y);

int main(void)
{
    int n, k; //location of subin and sister
    cin >> n >> k;
    cout << bfs(n, k);
}

int bfs(int x, int y)
{
    int time = 0; //the fastest time to find sister
    queue<int> q;
    q.push(x);
    
    while (1) {
        int size = q.size(); //if not equal to k, size increases
        
        for (int i = 0; i < size; i++) {
            x = q.front();
            q.pop();
            
            if (x == y) {
                return time;
            }
            
            if (0 <= x - 1 && visited[x - 1] == 0) {
                q.push(x - 1);
                visited[x - 1] = 1;
            }
            
            if (x + 1 <= 100000 && visited[x + 1] == 0) {
                q.push(x + 1);
                visited[x + 1] = 1;
            }
            
            if (2 * x <= 100000 && visited[2 * x] == 0) {
                q.push(2 * x);
                visited[2 * x] = 1;
            }
        }
        
        time++;
    }
}