백준 4375 - 1 (모듈러 연산)

13549번: 숨바꼭질 3 (acmicpc.net)

13549번: 숨바꼭질 3

풀이과정 및 주의사항

수빈이는 now*2 (순간이동) / now+1 / now-1 3가지 좌표 중 하나로 이동할 수 있습니다.

순간이동은 시간이 걸리지 않으며 / 한칸 이동 시 시간 + 1이 추가됩니다.

 

만약 순간이동 역시 시간이 1초 걸렸다면 단순히 bfs로 해결할 수 있었지만, 순간이동의 시간이 걸리지 않으므로

가중치를 최대로 주어서 풀어줬어야 했습니다.

따라서 일반적인 queue를 사용하지 않고 우선순위 큐(priority queue)를 사용하거나 deque(덱)을 사용해야 했는데

저는 우선순위 큐를 사용해서 풀이했습니다.

 

또한 가장 중요한 것은, 우선순위 큐를 사용한다고 끝나는 것이 아니라 순간이동에 대한 처리를 가장 먼저 해줘야 한다는 점입니다.

예를들어 만약 시작 좌표가 1이고 도착지점이 2라면, 순간이동으로 끝낼 수 있는데 now+1을 먼저 실행 시 1초가 걸리도록 답이 출력되기 때문입니다. 방문했던 지점은 다시 방문하지 않으므로 순간이동을 가장 먼저 처리해줘야 합니다.

 

코드

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

#define MAX_SIZE 100000

int N,K;
bool visited[MAX_SIZE+1];

int solution() {
    priority_queue < pair < int,int >, vector < pair < int,int > >, greater < pair < int,int > > > q;
    q.push({0,N});
    visited[N] = true;
    
    while(!q.empty()) {
        int depth = q.top().first;
        int now = q.top().second;
        q.pop();

        if(now == K) {
            return depth;
        }

        if (now * 2 <= MAX_SIZE && !visited[now * 2]) {
            q.push({ depth, now * 2 });
            visited[now * 2] = true;
        }
        if (now + 1 <= MAX_SIZE && !visited[now + 1]) {
            q.push({ depth + 1, now + 1 });
            visited[now + 1] = true;
        }
        if (now - 1 >= 0 && !visited[now - 1]) {
            q.push({ depth + 1 , now - 1 });
            visited[now - 1] = true;
        }
    }
}

int main() {
    scanf("%d %d", &N, &K);
    printf("%d\n", solution());
    return 0;
}