BOJ 16118

10 Feb 2020 • ProblemSolving

달빛여우

문제출처

문제 해석

  • 달빛여우가 달빛늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력하는 문제입니다.
  • N개의 나무 그루터기와 M개의 오솔길이 있습니다.
  • 달빛여우는 일정한 속도로 움직이고, 달빛늑대는 처음에 여우의 속도의 2배를 이동하다가 다음 오솔길에서는 여우 속도의 절반을 이동하는 것을 반복합니다.
  • 달빛여우가 달빛늑대보다 먼저 도착할 수 있는 나무 그루터기를 카운트 합니다.

설계(20)

  • 기본적으로 해당 문제는 다익스트라 알고리즘을 사용하는 문제입니다.
  • 여기서 다른점은 여우는 일정한 속도로 이동하고, 늑대는 여우*2, 여우/2를 반복이동하게 됩니다.
  • 절반의 값을 처리하기 용이하게 하기 위해서 오솔길의 길이 자체를 2배 처리합니다.
  • 여우에 대해서는 기본 다익스트라 알고리즘을 수행합니다.
  • 늑대의 경우에는 dist[MAXN]3를 이용하여, (dist[다음칸][1] > dist[현재칸][0]+ 상태에 따른 오솔길의 길이) 조건을 만족하는 경로를 찾게 구현합니다.
  • 여기서 주의할 점은 처음 dist를 초기화 할 때, dist[0][1], dist[0][0] 을 두개 다 0으로 초기화 하면 안됩니다. 이유는 다른 경로를 통해서 dist[0][0]을 지나는 경우 또한 고려해야 하기 때문입니다.

구현(60)

코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
#define MAXN 4000
typedef long long ll;
#define INF 1e15

vector<pair<int,int> > adj[MAXN];
int N,M;
ll dist[MAXN][3];

struct node{
    int cur;
    ll cur_w;
    int flag;

    bool operator < (const node& a) const{
        return a.cur_w < cur_w;
    };
};
priority_queue<node> pq;
void dijkstra(int mode){

    pq.push({0,0,mode});
    dist[0][mode] = 0;

    while (!pq.empty()){
        ll cur_w = pq.top().cur_w;
        int cur = pq.top().cur;
        int flag = pq.top().flag;
        pq.pop();
        if (dist[cur][flag] != cur_w) continue;

        for (int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i].first;
            ll next_w = (ll)adj[cur][i].second;
            if (mode != 2){
                if (!((flag+1)%2)) next_w/=2;
                else next_w *=2;
                if (dist[next][(flag+1)%2]> next_w + cur_w){
                    dist[next][(flag+1)%2] = next_w + cur_w;
                    pq.push({next,next_w+cur_w,(flag+1)%2});
                }
            }
            else{
                if (dist[next][flag]>next_w+cur_w){
                    dist[next][flag] = next_w+cur_w;
                    pq.push({next,next_w+cur_w,flag});
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    while (M--){
        int u,v,w;
        cin >> u >> v >> w;
        u--;
        v--;
        w*=2;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for (int i = 0 ; i < N; i++){
        for (int k = 0 ; k < 3; k++){
            dist[i][k] = INF;
        }
    }
    dijkstra(2);
    dijkstra(1);
    int ans = 0;
    for (int i =0; i < N; i++){
        if (dist[i][2]<min(dist[i][0],dist[i][1])) ans++;
    }
    cout << ans <<'\n';

    return 0;
}
디버깅
  • if (dist[cur][flag] != cur_w) continue 해당 코드를 작성하고 안하고의 차이가 극심하기 때문에 이를 구현하지 않을 경우에 시간초과가 났습니다.
  • 처음에 INF를 987654321로 지정했으나, 최악의 경우에 2NM보다 크기 때문에 1e15로 수정하였습니다.
  • 또한, 가중치 값의 범위가 int형을 넘어서기 때문에 long long형으로 변환하였습니다.
제출결과
  • 80ms

마무리

  • 다익스트라 알고리즘을 사용해야 한다는 것과 구현 아이디어는 어렵지 않게 생각을 했으나, 구현 과정중에 생각치 못한 요소들로 인해 디버깅에 시간을 많이 썼습니다.
 BOJ

Related Posts