# 1697. 숨바꼭질

관련 알고리즘 : BFS (너비 우선 탐색)

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

 

풀이과정

 

수빈이가 동생에게 가는 데 최단 경로(시간)을 구하는 문제이므로, BFS(너비 우선 탐색)을 이용한다.

 

1. 수빈이의 위치와 시간(처음 시작할 떄는 0) pair를 큐에 넣고,

2. bfs를 통해 수빈이 이동하는 방법( n+1 / n-1 / n*2 )을 check에 넣어 방문 여부 검사

3. 방문하지 않았다면 각각을 큐에 넣기

4. 하나씩 pop 하면서 이동 실행, 이동한 위치와 시간을 다시 큐에 푸시

5. 동생이 있는 위치에 도달 시,  이동한 시간 출력

 

여기서 주의할 점은, 방문했는지 여부를 검사하지 않으면 같은 작업을 중복으로 반복 할 가능성이 생기기 때문에 꼭 check를 통해 이를 검사해주어야 한다.

 

---

 

해결 코드 - C++

// 백준 1697 - 숨바꼭질

#include <iostream>
#include <queue>

using namespace std;

int n,k;
bool check[100001]; // 중복 검사 막기
int ans = 0; // 최종 시간

int main()
{
    cin >> n >> k;
    queue<pair<int, int>> que; // 수빈의 <위치,시간> 큐
    que.push(make_pair(n, 0)); // 초기 시작위치 n, 시간 0
    check[n] = true;

    while(!que.empty())
    {
        int pos = que.front().first; // 수빈의 위치
        int time = que.front().second; // 수빈의 이동시간
        que.pop();

        // 동생 위치에 도달 시 시간 전달 후 반복문 탈출
        if(pos == k)
        {
            ans = time;
            break;
        }

        // 조건(이동 시 문제에서 제한한 범위 내에 있는지 여부) 검사 후, 큐에 이동 후의 위치와 시간 넣기
        if(pos+1>=0 && pos+1<100001)
        {
            if(!check[pos+1])
            {
                check[pos+1] = true;
                que.push(make_pair(pos+1, time+1));
            }
        }
        if(pos-1>=0 && pos-1<100001)
        {
            if(!check[pos-1])
            {
                check[pos-1] = true;
                que.push(make_pair(pos-1, time+1));
            }
        }
        if(2*pos>=0 && 2*pos<100001)
        {
            if(!check[2*pos])
            {
                check[2*pos] = true;
                que.push(make_pair(2*pos, time+1));
            }
        }
    }

    cout << ans << endl;
    return 0;
}

 

문제 해결 이후 다른 사람들의 코드를 보니 make_pair 대신 emplace 함수를 쓴 경우가 많았다. 

검색해 보니 make_pair 등으로 객체를 만들고 push해줄 필요 없이 사용자가 이에 들어갈 요소들만 넣어줘도 알아서 객체를 만들어 넣어주는 것 같다.

 

que.push(make_pair(pos,time));
que.emplace(pos,time);

 

이런 식으로 쓰일 수 있는 듯 하다.