백준 13549 숨바꼭질 3

JunSeok·2023년 2월 25일
0

백준

목록 보기
25/40
  • 아이디어
    • 수빈이가 시작점부터 갈 수 있는 경우의 수에 최단 거리를 기록하면서 동생을 찾아나선다
    • BFS를 이용한다. 이는 1차원에서의 BFS문제
    • 수빈이의 위치는 200000을 넘을 수 있기 때문이 범위 고려해야 한다.
  • 문제발생
    • 2*X의 경우 이동시간이 증가하지 않기 때문에 최단거리가 아닌 값이 먼저 나올 수 있다.
  • 해결방법
    • 2*X를 반복문의 제일 앞에 위치한다.
    • 또는 deque을 사용해서 2*X를 push_front하고 나머지는 push_back하는 방법이 있다.

풀이 1

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

int n, k;
int dist[200002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    queue<int> Q;
    Q.push(n);
    dist[n] = 1;
    while(dist[k] == 0) {
        int cur = Q.front(); Q.pop();
        for(int next : {cur*2, cur-1, cur+1}) {
            if(next < 0 || next >= 200002) continue;
            if(dist[next] != 0) continue;
            if(next == cur*2) {
                dist[next] = dist[cur];
            } else dist[next] = dist[cur]+1;
            Q.push(next);
        }
    }
    cout << dist[k]-1;
}

풀이 2 (deque 사용)

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

int n, k;
int dist[200002];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    int MX = 200000;
    deque<int> dq;
    dq.push_back(n);
    dist[n] = 1;
    while(!dq.empty()) {
        int cur = dq.front(); dq.pop_front();
        if(2*cur < MX && dist[2*cur] == 0) {
            dist[2*cur] = dist[cur];
            dq.push_front(2*cur);
        }
        for(int nxt : {cur-1, cur+1}) {
            if(nxt < 0 || nxt >= MX || dist[nxt] != 0) continue;
            dist[nxt] = dist[cur]+1;
            dq.push_back(nxt);
        }
    }
    cout << dist[k]-1;
}
profile
최선을 다한다는 것은 할 수 있는 한 가장 핵심을 향한다는 것

0개의 댓글