[1697번] 숨바꼭질

대표적인 탐색문제, DFS와 BFS 중 어떤 탐색을 사용할 것인지 판단하는 것이 중요합니다.

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

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

[예제입력] 

5 (수빈이의 위치 N) 

17 (동생의 위치 K)

[예제출력]

4 (5-10-9-18-17)

[풀이를 위한 개념]

BFS (Breadth First Search)는 너비 우선 탐색으로 트리구조 데이터에서 같은 깊이에서 모든 점을 검사하고 다음 깊이로 내려가는 방식입니다.

BFS는 DFS(Depth First Search)와 다르게 스택 대신 큐(Queue)를 사용합니다.

[그림1] 왼쪽이 DFS, 오른쪽이 BFS이다. 왼쪽(DFS)은 한쪽 방향으로 깊숙하게 내려갔다가 다음 트리의 데이터로 이동하는 반면에 오른쪽(BFS)은 같은 깊이의 데이터를 모두 훑고 밑으로 내려간다.

BFS 는 다음과 같은 문제에 사용되는 알고리즘입니다.

1. 최소 상태의 개수가 1초보다 작아야 한다.

2. 최소비용을 구하는 문제

3. 이동간극(비용)이 1로 동일해야 한다.

BFS를 이용하기 위해서 Queue 자료구조의 개념을 숙지해야 합니다.

[그림2] 앞에서부터 차례대로 쌓이고 먼저 쌓인 데이터가 먼저 사라지는 방식. 그림과 같이 Front에 있는 데이터가 Dequeue(삭제, Return) 되고 Back에 있는 데이터가 Enqueue(추가) 된다. 대표적으로 리그오브레전드(LoL)에서 솔로큐(솔큐)를 돌린다는 의미도 이 개념에서 나온 말이다.     먼저 대기 하고 있는 유저가 먼저 게임을 진행할 수 있기 때문이다.

Queue는 먼저 들어온 자료가 먼저 빠진다는 원리에서 나온 이름입니다. Queue는 입장을 위해 줄을 서있는 것을 의미합니다.

의미상으로 선입선출이라고도 표현합니다.

[그림2]에서 표현된 큐는 '선형큐' 이고  자료가 많아져서 데이터 하나를 Dequeue(삭제,Return) 할 때마다 모든 큐의 데이터를 앞으로 이동시켜야 하는 번거로움을 없애기 위해 '원형큐'가 생겨났습니다.

[그림3] 원형큐는 시작과 끝이 이어져 있기 때문에 데이터 양이 정해져 있다면 나머지 데이터를 하나하나 앞으로 밀어야하는 번거로움이 사라진다.

다만 원형큐에서는 큐가 모두 비어있거나 모두 채워져있을 때 시작과 끝을 구분하기 힘들기 때문에 정해진 데이터에서 큐를 하나 더 추가해서 비어있는 큐를 만들어야 하는 유의점이 있습니다.

이제 문제로 돌아가서 문제를 트리형 데이터로 탐색하는 방법을 알아보겠습니다.

[풀이과정]

 

[그림1]과 같이 트리형 데이터로 문제를 그려 볼 수 있습니다. 그림으로 예제 문제의 답이 나오는 과정을 그려보겠습니다.

[그림3] 문제와 같이 각 점(nod)는 -1, +1, x2 의 세갈레 길로 나눠진다. 그리고 가장 먼저 답을 만나는 위치를 찾을 수 있다.

우리가 생각하는 문제풀이의 과정은 이렇게 진행되지만 코딩을 위해선 논리적인 순서로 다시 생각하는 것이 좋습니다. 코딩을 위한, 특히 Queue를 이용해 답이 나오는 과정을 그려보겠습니다.

[그림4] Queue가 추가되고 빠져나가는 과정을 컨베이어 벨트로 생각하면 쉽다. q.pop() 명령어로 상자를 떨어뜨려 버리고 q.push()로 새로운 상자를 만든다.

[그림4]를 보면 [그림3]의 트리를 시간 순서대로 표현했습니다. q.push()로 생성되는 값들은 q.pop()으로 지워지기 직전, 맨 앞에 있는 Queue (front queue)의 -1,+1,x2를 해준 값입니다. 이런 과정으로 [그림3]의 모든 점(nod)를 살펴볼 수 있고 가장 먼저 만나는 답을 찾게 되면 최소시간을 구할 수 있습니다.

[정답]

#include <iostream>
#include <queue>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int n;    //수빈이의 위치
    int k;    //동생의 위치
    
    scanf("%d", &n);
    scanf("%d", &k);
    
    queue <int> q;    //queue 생성
 
    //위치는 0~100000 까지 가능하므로 100001개의 배열이 필요하다
 
    bool visited[100001] = {0};        //들렀던 점은 다시 들르지 않는 것이 최소값의 효율에 좋으므로 배열로 방문한 곳을 체크한다.
    int time[100001] = {0};            //위치별 도달하기까지의 이동시간표시. 직전에 있던 곳에서의 이동시간의 합을 1씩 더하면서 표시하기 위한 배열.
    int now;
    
    visited[n] = 1;        //수빈이의 출발지는 들렀던 곳
    time[n] = 0;        
    q.push(n);            //수빈이의 위치 queue 삽입
    
    while(!q.empty())
    {
        now = q.front();    //맨 앞에 있는 queue 추출
        q.pop();            //맨 앞에 잇는 queue 제거, [그림4] 참조
        
        if(now == k)        //동생의 위치에 도달하는 순간 반복문을 빠져나감
        {
            break;
        }
        if(now - 1>=0 && visited[now-1] == 0)    // -1 연산 (-1 연산했을 때 0보다 커야하고, 들렀던 곳이 아니어야 함)
        {
            q.push(now-1);
            visited[now-1] = 1;
            time[now-1] = time[now] + 1;        // now-1 위치에 도달했으므로 '이동시간+1' , 'visited=1' 로  방문표시
        }
        if(now +1 <= 100000 && visited[now+1] == 0)        // +1 연산
        {
            q.push(now+1);
            visited[now+1] = 1;
            time[now+1] = time[now] + 1;
        }
        if(now*2 <= 100000 && visited[now*2] == 0)        // x2 연산
        {
            q.push(now*2);
            visited[now*2] = 1;
            time[now*2] = time[now] +1;
        }
    }
    printf("%d", time[k]);
    
}

1. 배열의 크기를 정하는 것은 생각보다 굉장히 중요하다. 자료구조 개념을 확실하게 정립하는 것 또한 중요. 100000개의 배열을 선언했다가 계속된 반례가 나왔다.

2. 배열을 전부 초기화 해주자. [] = {0}