유향 그래프에서 BFS, DP 사용하기 - ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

---

유향 그래프에서 인접 노드의 비용을 고려해 최대 소요 시간을 구하는 문제입니다. 문제 분류는 위상정렬로 되어있지만, 더 자주 쓰이는 BFS와 DP로 해결했습니다.

BFS (Breadth First Search)

전형적인 bfs 알고리즘 형태로 풀 수 있습니다. indegree가 0인 노드에서 최댓값을 체크하면 됩니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_N = 1000;
int n, k, w;
int dist[MAX_N + 1];
vector<vector<int> > adj;

int solve() {
    int ret = 0;
    int cost[n + 1] = { 0 }; // 각 노드의 누적 소요 시간
    queue<int> q;

    q.push(w);
    cost[w] = dist[w];

    while(!q.empty()) {
        int cur = q.front(); q.pop();
        int cur_cost = cost[cur];

        if(adj[cur].empty()) // indegree가 0인 경우 최댓값을 체크
            ret = max(ret, cur_cost);
        for(int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            int next_cost = cur_cost + dist[next];

            if(next_cost < cost[next]) continue; // 불필요한 삽입을 방지하기 위한 조건
            cost[next] = next_cost;
            q.push(next);
        }
    }

    return ret;
}

int main() {
    int tc; cin >> tc;

    while(tc--) {
        cin >> n >> k;
        adj.clear();
        adj.resize(n + 1);

        for(int i = 1; i <= n; i++) {
            scanf("%d", &dist[i]);
        }

        for(int i = 0, a, b; i < k; i++) {
            scanf("%d %d", &a, &b);
            adj[b].push_back(a);
        }

        cin >> w;
        cout << solve() << endl;
    }

    return 0;
}

DP (Dynamic Programming)

위 코드로는 1000ms정도의 스코어(제출 당시 기준)로 통과하는 것을 볼 수 있습니다. 하지만 더 빠른 스코어를 원한다면 다이나믹 프로그래밍을 시도할 수 있습니다. 아래 코드로는 190ms대의 스코어로 패스하는 것을 볼 수 있습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
int n, k, w;
int dist[MAX_N + 1];
int memo[MAX_N + 1]; // 메모이제이션을 위한 배열
vector<vector<int> > adj;

int solve(int cur) {
    int &ret = memo[cur];

    if(ret != -1) return ret;

    ret = 0;

    for(int i = 0; i < adj[cur].size(); i++) {
        ret = max(ret, solve(adj[cur][i])); // 각 인접 노드의 누적 소요 시간 중에서 최댓값을 탐색
    }

    return ret += dist[cur]; // 최대 누적 소요 시간에 현재 노드의 소요 시간을 더하고 반환
}

int main() {
    int tc; cin >> tc;

    while(tc--) {
        memset(memo, -1, sizeof(memo));
        cin >> n >> k;
        adj.clear();
        adj.resize(n + 1);

        for(int i = 1; i <= n; i++) {
            scanf("%d", &dist[i]);
        }

        for(int i = 0, a, b; i < k; i++) {
            scanf("%d %d", &a, &b);
            adj[b].push_back(a);
        }

        cin >> w;
        cout << solve(w) << endl;
    }

    return 0;
}