[BOJ 1697] (DFS/BFS)숨바꼭질 (C++)

숨바꼭질 (Silver 1)

문제

전체 문제 보기

1697번: 숨바꼭질

접근법

문제에서 수빈이와 동생의 위치는 1차원 수평선 위의 좌표로 주어진다. 그리고 수빈이의 위치가 x 일 때 다음으로 수빈이가 이동할 수 있는 위치는 x+1, x-1, x*2 이다. 이동할 수 있는 위치를 인접 노드라고 본다면 BFS로 풀이 가능한 문제이다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간도 BFS 탐색을 통해서 최단거리 찾는 방법과 동일하다.

자료구조 선택

본 문제를 BFS로 풀이하기 위해서 먼저 다음과 같이 Node를 정의하였다.

const int MAX = 100'001;
struct Node {
    Node(int _pos) : pos(_pos), depth(0), nextPos{}
    {
        // 이동할 수 없는 위치는 -1
        nextPos.fill(-1);

        // 이동할 수 있는 위치는 해당 위치의 좌표
        if (pos - 1 >= 0)
            nextPos[0] = pos - 1;
        if (pos + 1< MAX)
            nextPos[1] = pos + 1;
        if (pos * 2 < MAX)
            nextPos[2] = pos * 2;
    }

    int pos;
    int depth;
    array<int, 3> nextPos;
};

• pos: 각 노드 마다 현재의 위치 값을 가진다.
• depth: 각 노드마다 탐색의 깊이 값을 가져서 최단거리를 계산할 때 활용한다.
• nextPos[]: 인접 노드의 위치이다. 이동 가능한 인접 노드의 위치는 노드의 생성자에서 계산한다.

노드의 방문기록은 별도로 두지 않았다. 모든 좌표를 가지고 있는 배열을 만든 뒤 해당 좌표에 방문할 때만 노드를 생성하도록 구현할 계획이기 때문이다. 만약 해당 좌표에서 nullptr검사를 하여 노드가 생성되었다면 방문한 좌표이고, 노드가 생성되지 않았다면 아직 방문하지 않은 좌표라는 사실을 알 수 있기 때문이다.

구현

BFS를 활용하여 아래와 같이 구현할 수 있다. 스마트 포인터를 연습하기 위해서 동적으로 생성한 노드는 스마트 포인터로 관리하였
다. 동적으로 할당한 노드들은 nodes 배열이 해제될 때 함께 해제된다.

#include <iostream>
#include <array>
#include <queue>
#include <memory>

#define endl '\n'
using namespace std;

const int MAX = 100'001;
struct Node {
    Node(int _pos) : pos(_pos), depth(0), nextPos{}
    {
        // 이동할 수 없는 위치는 -1
        nextPos.fill(-1);

        // 이동할 수 있는 위치는 해당 위치의 좌표
        if (pos - 1 >= 0)
            nextPos[0] = pos - 1;
        if (pos + 1< MAX)
            nextPos[1] = pos + 1;
        if (pos * 2 < MAX)
            nextPos[2] = pos * 2;
    }

    int pos;
    int depth;
    array<int, 3> nextPos;
};
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, K;
    array<shared_ptr<Node>, MAX> nodes{};
    cin >> N >> K;

    // 위치가 같은 경우
    if (N == K) 
    {
        cout << 0;
        return 0;
    }
    queue<shared_ptr<Node>> q;

    nodes[N] = make_shared<Node>(N);
    q.push(nodes[N]);

    // BFS
    while (!q.empty())
    {
        shared_ptr<Node> cur;
        cur = q.front();
        q.pop();

        // 다음노드 탐색
        for(int next : cur->nextPos)
        {
            if (next == K)
            {
                cout << cur->depth + 1;
                return 0;
            }

            // 이동 할 수 없는 경우
            if (next == -1) continue;
            // 방문한 적이 있는 경우
            if (nodes[next] != nullptr) continue;

            nodes[next] = make_shared<Node>(next);
            nodes[next]->depth = cur->depth + 1;
            q.push(nodes[next]);
        }
    }

    return 0;
}