[BOJ알고리즘, C++]#1697_숨바꼭질, 그래프 탐색, BFS

 

#1. 문제

1697번: 숨바꼭질

 

---

 

#2. 풀이

 

1. 그래프 탐색

[자료구조]#6_그래프

 

그래프의 모든 정점을 탐색하는 방법은 두 가지입니다. 먼저, DFS(깊이 우선 탐색)은 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 먼저 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택을 활용하여 구현합니다. 다음으로, BFS(너비 우선 탐색)은 현재 정점과 인접한 정점들을 우선 탐색하는 방법입니다. BFS는 일반적으로 큐를 활용하여 구현합니다.

 

2. 각 정점은 인접 정점으로 이동할 수 있는 세 가지 간선이 존재한다고 가정하자!

 

1. 주어진 출발 정점을 기준으로 BFS를 수행합니다.
2. 이때, 각 정점의 인접 정점을 순회할 때, +1 정점, -1 정점, 그리고 * 2 정점, 총 세 가지 인접 정점을 탐색합니다. 이때, 각 정점은 해당 정점까지 이르는 경로에서 걸린 시간을 기억해 줍니다.
3. 마지막으로, 도착 정점에 도착하였을 때, 최소 시간을 반환하고 출력해 줍니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int N, K;
int moveType[3] = {1, -1, 2};

void bfs()
{
    int minTime = 0;
    queue<p> q;
    vector<bool> visited(100001, false);

    q.push({N, 0});
    visited[N] = true;

    while (!q.empty())
    {
        int cPos = q.front().first;
        int cTime = q.front().second;
        q.pop();

        if (cPos == K)
        {
            minTime = cTime;
            break;
        }

        for (int i = 0; i < 3; ++i)
        {
            // 다음 위치 계산
            int nPos;
            if (i < 2)
            {
                nPos = cPos + moveType[i];
            }
            else
            {
                nPos = cPos * moveType[i];
            }
            // 방문 여부 + 범위 내 존재하는지 여부
            if (nPos >= 0 && nPos <= 100000 && !visited[nPos])
            {
                visited[nPos] = true;
                q.push({nPos, cTime + 1});
            }
        }
    }

    cout << minTime;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    bfs();

    return 0;
}

 

---