[BOJ] 24888 : 노트 조각

문제 링크

24888번: 노트 조각 (acmicpc.net)

24888번: 노트 조각

숭고한 Division2 F번 문제.

풀이

jhnah917은 반드시 최단경로로 가기때문에 참가자 lobo_prix가 우승하기 위해서는 공동우승을 하는 수밖에 없다.

즉, 최단거리로 가는 경로 중에 모든 노트조각을 줍고 갈 수 있는 경로를 찾는 문제.

최단거리로 가는 경로가 여러개 존재하기 때문에 모든 경로를 돌아보는 수밖에 없었다. 다익스트라 알고리즘을 이용해서 경로를 탐색하는데 기존의 경로보다 비용이 크거나 기존의 경로와 비용이 같지만 주울 수 있는 노트조각의 수가 적다면 비효율적인 경로라고 판단했다. 우선 순위큐를 이용하기때문에 기존 경로보다 비용이 적게들 수는 없다. 이미 탐색된 경로가 비용적인 면에서는 가장 효율적인 경로다. 그렇기 때문에 기존 경로가 존재한다면 기존 경로와 비용이 같고, 노트조각을 같거나 더 많이 주울 수 있다면 유효한 경로라고 판단하는 것이다.

dist라는 배열을 pair로 선언해서 {비용, 노트조각 수} 이렇게 저장해두었다. 초기값은 {INF, 0}으로 초기화 시켜놓은 상태이다.

if (dist[now].first < cost)
		continue;
dist[now].first = cost;
if (dist[now].second <= cnt) {
	dist[now].second = cnt;
	Before[now] = before;
}
else continue;

이 코드를 통해서 기존의 경로와 비교해 유효한 경로인지 판단해주었다. 당연히 해당 정점을 처음 방문한 것이라면 유효한 경로가 된다.

그리고 Before 배열을 이용해서 방문한 지점의 순서를 역추적했다.

처음에는 기존의 경로와 노트조각의 수가 같아도 continue를 통해 스킵했다. 하지만 그렇게 하면 모든 경로를 탐색하지 못한다. 그렇기 때문에 노트조각의 수가 같아도 유효한 경로라고 판단하고 탐색을 이어간다.

이렇게 다익스트라 알고리즘을 마친 후 N 정점까지 왔을 때 주울 수 있는 최대 노트조각의 수가 모든 노트조각의 수와 같으면 참가자가 우승할 수 있는 경로가 존재한다는 의미다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll,int>, pair<int,int>>, vector<pair<pair<ll,int>, pair<int,int>>>, greater<pair<pair<ll,int>, pair<int,int>>>> Priority_queue;
const long long INF = LLONG_MAX;
const int MAX_N = 200000 + 5;
int N, M;
vector<pair<ll,int>> dist;
vector<pair<int, ll >> Edge[MAX_N];
int Before[MAX_N];
int Note[MAX_N];
 
void dijkstra(int st, int ed);
void Init();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    dist.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        Edge[a].push_back({ b,w });
        Edge[b].push_back({ a,w });
    }
    int cnt_Note = 0;
    for (int i = 1; i <= N; i++) {
        cin >> Note[i];
        if (Note[i])
            cnt_Note++;
    }
    Init();
    dijkstra(1, N);
 
    if (dist[N].second == cnt_Note) {
        vector<int> track;
        int idx = N;
        while (idx != -1) {
            track.push_back(idx);
            idx = Before[idx];
        }
        cout << track.size() << "\n";
        for (int i = track.size() - 1; i >= 0; i--)
            cout << track[i] << " ";
        cout << "\n";
    }
    else cout << "-1\n";
    return 0;
}
 
void Init() {
    for (int i = 0; i <= N; i++) {
        dist[i].first = INF; //거리
        dist[i].second = 0; //노트 조각
    }
}
 
void dijkstra(int st, int ed) {
    Priority_queue pq;
    if (Note[st])
        pq.push({ {0,st},{1,-1} });
    else pq.push({ {0,st},{0,-1} });
 
    while (!pq.empty()) {
        int now = pq.top().first.second;
        ll cost = pq.top().first.first;
        int cnt = pq.top().second.first;
        int before = pq.top().second.second;
        pq.pop();
 
        if (dist[now].first < cost)
            continue;
        dist[now].first = cost;
        if (dist[now].second <= cnt) {
            dist[now].second = cnt;
            Before[now] = before;
        }
        else continue;
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            ll acost = cost + Edge[now][i].second;
            int next_cnt = cnt;
            if (Note[next])
                next_cnt++;
            if (dist[next].first < acost)
                continue;
            if (dist[next].second > next_cnt)
                continue;
            pq.push({ {acost,next},{next_cnt, now} });
        }
    }
}
 

몇몇 문제들은 충분히 시간을 갖고 풀면 풀 수 있는 문제들인데 대회때는 압박감때문인지 못풀었다. 시간내에 문제를 푸는 연습을 해야할 것같다. ㅍㅇㅌ!