[백준] 1697번 숨바꼭질

문제: 1697번: 숨바꼭질

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


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

    int n, k; // n: 수빈이 위치, k: 동생 위치
    cin >> n >> k;

    // first: 위치, second: cnt
    queue<pair<int, int>> nexts;
    vector<int> visits(100001);

    int dx[3] = { -1, 1, 2 };

    nexts.push(make_pair(n, 0));
    visits[n] = 1; // 방문 표시

    while (!nexts.empty()) {
        int nSize = nexts.size();

        while (nSize-- > 0) {
            pair<int, int> cur = nexts.front();
            if (cur.first == k) {
                cout << cur.second;
                return 0;
            }

            nexts.pop();

            for (int i = 0; i < 3; i++) {
                int nx;
                
                if (dx[i] == 2)
                    nx = cur.first * 2;
                else
                    nx = cur.first + dx[i];

                if (nx < 0 || nx > 100000) continue;
                if (visits[nx] == 1) continue;

                visits[nx] = 1; // 방문 표시
                nexts.push(make_pair(nx, cur.second + 1));
            }
        }
    }
   
    return 0;
}

 

그냥 BFS 를 1차원에 적용해서 풀면 쉽게 해결할 수 있는 문제였다. 방문 표시를 해줘서 이미 방문한 곳이면 못 가도록 해주는 것도 기존 2차원의 BFS 방법과 똑같다.

 

만약 4에 방문하려고 하는데 이미 방문한 곳이면 가면 안되도록 해야 하는 이유를 생각해봤는데, 이미 4에 방문 표시가 되어 있다는 건 이미 지금보다 빠른 4로 가는 방법이 있었다는 것이다.

 

4로 가봤자 4에서 정답으로 최소 횟수로 가는 방법은 똑같으니까 갈 필요가 없는 것이다. 가봤자 최소 방법보다 횟수가 많아질뿐이다. 

 

머리로는 알았는데 설명하려고 하니까 어렵다. 어휘력이 부족해서..

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS