[C++] 1697번 : 숨바꼭질

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

 

요즘 BFS를 공부하고 있다.

BFS는 너비우선탐색으로 알고리즘의 흐름은 아래와같다.

 

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4.  큐가  빌 때까지 2번을 반복
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)

 

기본 틀은 BFS지만 예외처리에 신경을 써야했다.

처음에 pair쓰고 별 주접을 다떨었는데, 괜히 복잡해지고 헷갈려서 일차원배열로 싹다갈아 풀었다.

처음 초기화를 -1로 하는 비상한 생각을 하는게 나는 아직 너무 어렵다..ㅠㅠ

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pii pair<int, int>

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

vector<int> m(100001, -1);

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    m[n]++;

    queue<int> q;
    q.push(n);
    m[n] = 0;

    while (!q.empty())
    {
        auto curr = q.front();
        q.pop();

        if (curr == k)
        {
            cout << m[curr];
            break;
        }
        // x-1 : 만약 범위 안에 있고, 해당 좌표에 방문한 적이 없다면
        if (curr - 1 >= 0 && m[curr - 1] == -1)
        {
            // 후보에 추가한다.
            q.push(curr - 1);
            m[curr - 1] = m[curr] + 1;
        }

        // x+1 : 만약 범위 안에 있고, x+1에 방문한 적이 없다면
        if (curr + 1 <= 100000 && m[curr + 1] == -1)
        {
            q.push(curr + 1);
            m[curr + 1] = m[curr] + 1;
        }

        // 2*x : 만약 범위 안에 있고, 방문한 적이 없다면
        if (curr * 2 <= 100000 && m[curr * 2] == -1)
        {
            q.push(curr * 2);
            m[curr * 2] = m[curr] + 1;
        }
    }
}