www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

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

www.acmicpc.net

 

숨바꼭질 2와 다르게 3은 cur * 2 지점으로 텔레포트할 때에 시간이 소요되지 않는다.

평범하게 큐로 bfs 할 경우 기존 cur -1, cur + 1을 하면서 K에 도착하게 되면

이후에 cur * 2 를 통해 도착하는 시간보다 더 크지만 이미 방문처리가 되어있으므로 값을

갱신시켜줄 수 없다.

 

어떻게 접근해야될까?

 

이 문제는 우선순위 큐를 최소 힙으로 선언한 후 time을 기준으로 정렬하게 해 주면 된다.

그러면 cur에 대해서 가장 짧은 time을 가진 노드를 먼저 방문해주게 된다.

 

 

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
#include <iostream>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
int a[100001], n, k;
bool vis[100001];
priority_queue<pii, vector<pii>, greater<pii>> q;
 
int main() {
    cin >> n >> k;
 
    q.push({ 0,n });
    vis[n] = true;
 
    while (!q.empty()) {
        int cur = q.top().second;
        int time = q.top().first;
        q.pop();
        if (cur == k) break;
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) {
                vis[i] = true;
                if (i == cur * 2) {
                    a[i] = a[cur];
                    q.push({ time,i });
                }
                else {
                    a[i] = a[cur] + 1;
                    q.push({ time + 1,i });
                }
            }
        }
    }
 
    cout << a[k] << endl;
 
    return 0;
}
 cs

 

기존 bfs코드와 다를 것 없이 priority_queue로만 바꿔주면 된다.

 

또 다른 방법이 있다. 바로 deque자료구조를 이용하는 것인데, deque는 priority_queue를 이용하는 것보다

더 빠르게 구할 수 있다!!

 

우선순위 큐의 특성상 삽입하는 데에 O(logN)의 시간 복잡도가 걸린다. 그러나 가중치가 0-1로만

이루어진 상황이라면 현재 위치 cur에서 다음에 이동할 부분은 0 또는 1만 차이 난다는 것을 알 수 있다.

 

그러니 deque의 앞쪽 부분에는 텔레포트(cur * 2) 하는 부분을 삽입해주고 cur - 1, cur + 1 부분은 1초가 걸리니

뒤에 삽입해주면 된다.

 

deque의 특성상 앞 뒤로 삽입하는 경우는 O(1)이 걸리므로 더 빠르게 구할 수 있다.

 

 

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
#include <iostream>
#include <deque>
using namespace std;
 
int n, k;
int vis[100001];
deque<int> dq;
 
int main() {
    cin >> n >> k;
 
    dq.push_back(n);
    vis[n] = 0;
 
    while (!dq.empty()) {
        int cur = dq.front(); dq.pop_front();
        if (cur == k) break;
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) {
                vis[i] = true;
                if (i == cur * 2) {
                    dq.push_front(i);
                    vis[i] = vis[cur];
                }
                else {
                    dq.push_back(i);
                    vis[i] = vis[cur] + 1;
                }
            }
        }
    }
 
    cout << vis[k] << endl;
 
    return 0;
}
 cs

'BOJ' 카테고리의 다른 글

BOJ 1713 후보 추천하기  (0) 2021.01.01
BOJ 13913 숨바꼭질 4  (0) 2020.12.28
BOJ 12851 숨바꼭질 2  (0) 2020.12.28
BOJ 15686 치킨 배달  (0) 2020.12.25
BOJ 3190 뱀  (0) 2020.12.19

www.acmicpc.net/problem/12851

 

12851번: 숨바꼭질 2

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

www.acmicpc.net

 

며칠 고민해봤는데 풀이 방법이 안 떠올라서 다른 블로그를 참고해서 풀었다.

두 개 정도의 풀이 방법이 있었는데 하나는 K로 가는 방법의 수를 배열 하나를 더 만들어서 접근하는 방법이고

다른 하나는 큐에서 팝 할 때 방문 체크를 해주는 방식이다.

 

첫 번째 방법은 시간이 항상 1씩 늘어난다는 것을 이용해서 d[next] == d[cur] + 1 이라면 cnt를 증가시키는 방법이다.

두 번째 방법은 현재 위치에서 팝 할때 방문처리를 해준다면 목적지 K는 항상 들어갈 수 있으므로

큐에 넣어주고 현 위치가 K이고 방문한 시간이 같다면 cnt를 증가시켜주는 방법이다.

 

 

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
#include <iostream>
#include <queue>
using namespace std;
 
int a[100001], cnt[100001], n, k;
bool vis[100001];
queue<int> q;
 
int main() {
    cin >> n >> k;
 
    vis[n] = true;
    q.push(n);
    cnt[n] = 1;
 
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000) {
                if (!vis[i]) {
                    vis[i] = true;
                    q.push(i);
                    a[i] = a[cur] + 1;
                    cnt[i] = cnt[cur]; //이동가능하다면 현재까지의 경우의수 삽입
                } //현재 거리에서 1 더한값이 같다는 것은 이동 가능하다는 소리
                else if (a[i] == a[cur] + 1) cnt[i] += cnt[cur]; //경우의수 추가
            }
        }
    }
 
    cout << a[k] << endl;
    cout << cnt[k] << endl;
 
    return 0;
}
 cs

 

두 번째 코드

 

 

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
#include <iostream>
#include <queue>
using namespace std;
 
int n, k, cnt, time;
bool vis[100001];
queue<pair<int, int>> q;
 
int main() {
    cin >> n >> k;
 
    q.push({ n,0 });
    vis[n] = true;
 
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        vis[cur.first] = true;
        if (!time && cur.first == k) time = cur.second, ++cnt;
        else if (time == cur.second && cur.first == k) ++cnt;
        for (int i : {cur.first - 1, cur.first + 1, cur.first * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) q.push({ i,cur.second + 1 });
        }
    }
 
    cout << time << endl;
    cout << cnt << endl;
 
    return 0;
}
 cs

'BOJ' 카테고리의 다른 글

BOJ 13913 숨바꼭질 4  (0) 2020.12.28
BOJ 13549 숨바꼭질 3  (0) 2020.12.28
BOJ 15686 치킨 배달  (0) 2020.12.25
BOJ 3190 뱀  (0) 2020.12.19
BOJ 1446 지름길  (0) 2020.12.16

 

글이 복잡하게 쓰여있지만 이해하기 그리 어렵지 않다.

result에 실패율이 높은 순으로 정렬해서 return 해주면 되는데 어떻게 실패율을 구할 것인가가 중요하다

우선 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 인데

현재 스테이지 개수 / 현재보다 크거나 같은 스테이지의 개수로 치환 가능하다.

 

따라서 전처리를 통해 stages의 원소들이 몇 번 등장했는지와 가장 큰 값을 구해놓는다.

가장 큰 값은 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다. 조건 때문에 필요한데

for 문을 돌리면서 i 값이 가장 큰 값보다 크다면 실패율을 0으로 push 해줘야 하기 때문이다.

 

pair벡터를 <int, double>로 선언해주는데 idx와 fail rate를 담는다.

 

첫 번째 예제를 보면

각각의 번호와 몇 번 등장했는지를 구해보면 이렇게 나오는데

스테이지의 총인원수가 8명이니

<1,1> <2,3> <3,2> <4,1> <5,0> <6,1> 

 

에서 1번의 실패율은 1의 second / n - sum(누적)이다.

 

 

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
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[501];
 
bool comp(pair<int, double>& a, pair<int, double>& b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int, double>> a; // idx, fail rate
    int n = stages.size();
    for (int i : stages) d[i]++;
    int m = *max_element(stages.begin(), stages.end());
    
    int sum = 0;
    for (int i = 1; i <= N; ++i) {
        if (i > m) a.push_back({ i,0 });
        else a.push_back({ i,(double)d[i]/(n - sum) });
        sum += d[i];
    }
    sort(a.begin(), a.end(), comp);
    
    for (auto i : a) answer.push_back(i.first);
    
    return answer;
}
 cs

 

정렬은 comp를 통해 쉽게 구현 가능하다.

'Programmers' 카테고리의 다른 글

프로그래머스 기능개발  (0) 2020.12.11
C++ 단어 변환  (0) 2020.11.28
[프로그래머스 C++] 카카오프렌즈 컬러링북  (0) 2020.09.28
[프로그래머스 C++] 소수 찾기  (0) 2020.09.27
[프로그래머스 C++] 완주하지 못한 선수  (0) 2020.09.26

+ Recent posts

티스토리툴바