자동차경주( BOJ 2611 )

문제(2004 중등) : https://www.acmicpc.net/problem/2611

2611번: 자동차경주

 

문제 파악하기

1번 지점부터 자동차가 출발해서 1번 지점으로 되돌아오는 여러 경로 중 점수를 가장 많이 쌓는 경로를 찾는 문제입니다. 모든 경로는 같은 지점을 도달하지 않게 설계되어있으며, 어느 지점에서든 1번 지점으로 돌아올 수 있다고 합니다. 이는 곧 cycle이 없다고 해석할 수 있습니다. 따라서 가장 먼저 생각할 수 있는 방법은 우선순위 큐를 사용해서 1번 지점으로 돌아오는 모든 경우를 구하는 방법입니다. 다만, 이 방법은 몇몇 테스트케이스에 대해서 너무 오랜 시간이 걸려 TLE을 만들 수 있습니다. 그럼 어떤 방법을 사용할 수 있을까요?

 

문제 해결하기

우리는 문제에서 제시한 경로를 유심히 볼 필요가 있습니다. 제시된 경로에서 1번 지점에서 갈 수 있는 경로를 모두 지워보세요. 그럼 그래프가 어떻게 바뀌나요? 1번 지점에서 출발하는 경로를 지우면 우리는 모든 지점이 1번으로 향하는 방향 그래프를 얻을 수 있습니다. 이렇게 생긴 그래프를 효율적으로 탐색하는 방법은 바로 위상 정렬(top sort)를 이용하면 됩니다. 위상 정렬은 이전에 선행될 작업이 없는 작업부터 탐색을 시작해서 마지막 작업까지 처리할 때, 소요되는 비용을 구할 수 있는 알고리즘입니다. 이 알고리즘은 cycle이 형성되지 않는 방향 그래프에서 사용할 수 있으며, 다행히 우리가 풀 문제에서 주어지는 그래프 역시 cycle을 형성하지 않습니다. 그렇기에 이 문제는 위상 정렬을 사용하면 빠르게 해결할 수 있습니다.

 

우선, 위상 정렬을 사용하기 위해서는 선행되는 작업 여부를 확인해야 합니다. 보통은 enter[i] 배열을 사용해서 enter[i]의 값이 0이라면 i번을 큐에 넣고 탐색을 시작합니다. 큐에서 진행되는 탐색의 과정은 다음과 같습니다. 우선, 현재 작업이 영향을 미치는 다음 작업을 확인합니다. 즉, 우리 문제에서는 현재 지점에서 갈 수 있는 다음 지점(nxt)의 값을 확인합니다. 그리고 현재 값에서 다음 지점(nxt)을 가면서 얻을 수 있는 점수의 최댓값을 다음 지점에 저장합니다. 그리고 탐색을 마치면서 작업을 완료했기에 enter[nxt]의 값을 하나 줄여줍니다. 만약 줄인 다음에 enter[nxt]의 값이 0이라면 nxt를 큐에 넣어줍니다. 위의 4가지 과정을 반복하면 우리는 마지막 작업인 1번 지점까지 도달할 수 있습니다.

 

이렇게 1번 지점까지 도달한 다음에는 이동한 경로를 구할 차례입니다. 경로는 지금까지의 과정을 거꾸로 되추적하면 얻을 수 있으며, 이는 점수를 기록하면서 해당 점수를 기록하기 전의 위치를 같이 저장하면 됩니다. 예를 들어 2번 지점에서 5번 지점을 확인할 때, 현재 5번 지점에서 얻을 수 있다고 기록한 점수인 15점보다  더 큰 값인 17점을 얻을 수 있다면 5번 지점에는 17과 2를 같이 저장합니다. 그리고 나중에 되추적할 때에는 앞서 기록한 지점인 2번 지점으로 하나씩 이동하면 모든 경로를 구할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#define NMAX 1010
#define PAIR pair<int, int>
using namespace std;
 
int N, M, a, b, c;
vector< PAIR > adj[NMAX];
 
stack< int > st;
int cur, ccost, nxt, ncost;
 
queue< int > q;
PAIR cst[NMAX];
int enter[NMAX];
 
void tracking(int p) {
    if(p == 1) return;
    else {
        tracking(cst[p].second);
        printf("%d ", p);
    }
}
 
int main() {
    // input
    scanf("%d", &N);
    scanf("%d", &M);
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({b, c});
 
        enter[b]++;
    }
 
    // 초기 설정
    for(PAIR cur:adj[1]) {
        cst[cur.first] = make_pair(cur.second, 1);
        enter[cur.first]--;
    }
 
    // 초기 탐색값 넣기
    for(int i=1;i<=N;i++) {
        if(!enter[i]) q.push(i);
    }
 
    // 탐색(top sort)
    while(!q.empty()) {
        cur = q.front();
        ccost = cst[cur].first;
        q.pop();
 
        if(cur == 1) break;
 
        for(PAIR p:adj[cur]) {
            nxt = p.first;
            ncost = ccost + p.second;
 
            if(cst[nxt].first < ncost) cst[nxt] = make_pair(ncost, cur);
 
            enter[nxt]--;
            if(!enter[nxt]) q.push(nxt);
        }
    }
 
    // 최댓값 출력
    printf("%d\n", cst[1].first);
 
    // 이전 지점 백트래킹
    printf("%d ", 1);
    tracking(cst[1].second);
    printf("%d", 1);
 
}

후기

흔한 작업 문제가 아닌 그래프를 수정해서 위상 정렬하는 문제는 처음 봐서 신선한 느낌이었습니다. 처음 문제를 풀 때에는 다익스트라를 수정한 알고리즘으로 접근했는데 TLE이 나와서 잠시 당황한 기억이 있네요. 그래프 및 되추적을 연습할 때 좋은 문제라고 생각합니다.