백준 문제

백준 12851 (숨바꼭질 2) c++

kangyuseok 2022. 9. 14. 16:45
728x90

문제

 

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

숨바꼭질 과 유사한 문제입니다.

대신 최소 시간의 경우의 수를 세는 조건이 추가되었습니다.

예를들어 5에서 17로 간다고 하면

1. (5 -> 10 -> 9 -> 18 -> 17)

2. (5 -> 4 -> 8 -> 16 -> 17)

총 2가지가 존재합니다.

 

처음에 재귀함수를 구현하여 해결하려 했지만 구현하지 못했습니다.

그 다음 bfs로 접근해 보았습니다.

 

cin >> n >> k;

	queue < pair<int, int>>q;
	q.push({ n, 0 });
	while (!q.empty()) {
		int d = q.front().first;
		int time = q.front().second;
		
		visit[d] = true;
		if (way && d == k && t == time)
			way++;
		if (!way && d == k) {
			t = time;
			way++;
		}

		q.pop();
		if(d-1>=0 && time+1 <=t && !visit[d-1])
			q.push({ d - 1, time + 1 });
		if (d + 1 <= k && time + 1 <= t && !visit[d+1])
			q.push({ d + 1, time + 1 });
		if (d * 2 <= 100000 && time + 1 <= t && !visit[2*d])
			q.push({ d * 2, time + 1 });
	}
	cout << t << '\n' << way;

전체 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, k;
int t=MAX, way;
bool visit[200001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> k;
 
    queue < pair<int, int>>q;
    q.push({ n, 0 });
    while (!q.empty()) {
        int d = q.front().first;
        int time = q.front().second;
        
        visit[d] = true;
        if (way && d == k && t == time)
            way++;
        if (!way && d == k) {
            t = time;
            way++;
        }
 
        q.pop();
        if(d-1>=0 && time+1 <=t && !visit[d-1])
            q.push({ d - 1, time + 1 });
        if (d + 1 <= k && time + 1 <= t && !visit[d+1])
            q.push({ d + 1, time + 1 });
        if (d * 2 <= 100000 && time + 1 <= t && !visit[2*d])
            q.push({ d * 2, time + 1 });
    }
    cout << t << '\n' << way;
    
 
    return 0;
}
 
cs