[백준][C++] 12581번: 숨바꼭질 2 <199>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

12851번: 숨바꼭질 2

생강의 흐름

기존 숨바꼭질 문제에서는 한번 방문한 지점은 다시 큐에 넣지 않았었다.

 

하지만 숨바꼭질 2 문제에서는 방법의 가지수까지 고려해야하므로 Queue에서 pop할 때 해당 지점을 방문했다고 표시하는 것이 핵심이다.

예를 들어, N=1 K=4를 입력할 경우,

1) 1 -> (1+1) -> (2*2)

2) 1 -> (1*2) -> (2*2)

 

4에 도달하는 방법은 총 두가지 방법이 있습니다.

이때 만약 숨바꼭질 1 문제를 풀때 처럼 Queue에 삽입할때 방문 처리를 해버리면, 2번 case는 확인할수가 없게됩니다.

1번 case때 이미 방문 처리 되어버렸거든요!

 

따라서, Queue에 push할 때가 아닌 pop할 때 방문지점을 표시하면 쉽게 풀 수 있는 문제였습니다!

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001

int N, K;
int res;
int cnt;
bool visited[MAX];

void BFS(int num) {
    queue<pair<int, int>> q;

    visited[num] = true;
    q.push({num, 0});
    
    while(!q.empty()) {
        int nowPosition = q.front().first;
        int nowSec = q.front().second;
        q.pop();
        visited[nowPosition] = true;
        if(cnt && nowPosition == K && nowSec == res) cnt++;

        if(!cnt && nowPosition == K) { // 처음 동생한테 도착한경우
            res = nowSec;
            cnt++;
        }

        if(nowPosition + 1 < MAX && !visited[nowPosition+1]) {
            q.push({nowPosition+1, nowSec+1});
        }

        if(nowPosition - 1 >= 0 && !visited[nowPosition-1]) {
            q.push({nowPosition-1, nowSec+1});
        }

        if(nowPosition * 2 < MAX && !visited[nowPosition*2]) {
            q.push({nowPosition*2, nowSec+1});
        }
    }
}

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

    cin >> N >> K;
    BFS(N);

    cout << res << "\n" << cnt;

    return 0;
}