알고리즘 :: 백준 :: BFS :: 13549 :: 숨바꼭질3

문제

문제접근

문제 이해

알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.

• 저번 문제와 차이점은 단 하나입니다. 순간이동이 1초 → 0초로 바뀌었습니다.

해결 1

• 이 문제는 1697번 풀이에서 순간이동에 대한 코드에서 push()할 때 시간을 더해주지 않는 것으로 바꾸기만 하면 AC를 받을 수 있습니다.
• 왜냐하면 제가 세 액션 중 순간이동을 가장 먼저 조건문에 넣었기 때문입니다.
• 즉, 우연에 의한 AC입니다. 정식 풀이는 해결 2가 맞습니다.

해결 2

• 우리가 BFS를 이용해서 최소시간/최단거리 문제를 풀 수 있는 이유는 가중치가 1이라는 것이 보장되기 때문입니다.
• 앞으로 이동해도, 뒤로 이동해도 심지어 순간이동을 하더라도 이전까지는 1초만 소요됐지만, 이제는 순간이동은 가중치가 0입니다.
• 따라서 같은 임의의 점 x라고 할지라도, 가중치 1로 온 것과 가중치 0으로 온 것은 다르므로 서로 다른 점이라고 판단해야 합니다.
  • 왜냐하면, 1초 소요해서 도착한 x와 0초 소요해서 도착한 x를 기존의 queue로는 구분할 수 없기 때문입니다.
  • 따라서 이 문제는 가중치 0에 대한 queue와 가중치 1에 대한 queue 2개를 사용해야 하는 문제입니다.
  • 우리는 deque이라는 자료구조가 queue를 앞뒤로 합쳐놓은 형태의 자료구조임을 알고있습니다.
  • 따라서 이 문제는 deque 자료구조를 사용해서 가중치가 0일 때는 push_front()를, 가중치가 1일 때는 push_back()을 하는 방식으로 풀이합니다.
• deque의 앞쪽에는 가중치가 0인 행동들이 들어가므로 가장 먼지 목표지점 K에 도착하면 loop를 탈출해도 됩니다.
• 우리는 이번 문제를 통해 가중치가 0 또는 1인 최단거리/최소시간 문제에서는 BFS를 사용하되 queue가 아닌 deque을 사용해야한다는 점을 배울 수 있습니다.

코드

#include <iostream>
#include <deque>
#define MAX 100001
using namespace std;
int N, K;
bool visited[MAX];

int solve() {
    deque<pair<int,int>> q;
    q.push_front({N, 0});

    while(!q.empty()){
        int pos = q.front().first, t = q.front().second;
        if(pos == K) return t;
        int goPos = pos + 1, backPos = pos - 1, telePos = 2 * pos;
        q.pop_front();
        if(telePos < MAX && !visited[telePos])	// 순간이동
            visited[telePos] = true, q.push_front({telePos, t});
        if(backPos >= 0 && !visited[backPos])	// 한 칸 뒤로 이동
            visited[backPos] = true, q.push_back({backPos, t + 1});
        if(goPos < MAX && !visited[goPos])	// 한 칸 앞으로 이동
            visited[goPos] = true, q.push_back({goPos, t + 1});
    }
}
int main(){
    cin >> N >> K;
    cout << solve() << '\n';
}

결과