[백준] 1005번 - ACM Craft

• 문제 링크 : https://www.acmicpc.net/problem/1005

문제 풀이

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
#define INF 987654321
using namespace std;


int n, k;
vector<int> cost;
vector<int> visited;
vector<vector<int>> graph;
vector<int> output;

int dfs(int idx) {
    if (visited[idx])
        return visited[idx];
    if (!output[idx]) {
        visited[idx] = cost[idx];
        return visited[idx];
    }
    visited[idx] = 0;
    for (int nxt = 0; nxt < graph[idx].size(); nxt++) {
        int next = graph[idx][nxt];
        visited[idx] = max(dfs(next)+cost[idx], visited[idx]);
    }
    return visited[idx];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T; cin >> T;
    while (T--) {
        cin >> n >> k;
        cost = vector<int>(n + 1);
        visited = vector<int>(n + 1, 0);
        graph = vector<vector<int>>(n + 1);
        output = vector<int>(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            cin >> cost[i];
        }



        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            graph[b].push_back(a);
            output[b] += 1;
        }

        int w; cin >> w;
        int res = dfs(w);
        cout << res << endl;


    }



    return 0;
}

• 해당 문제는 위상 정렬 문제로 판단하고 우선 작성하였습니다.
• 다만 위의 풀이대로 작성할 경우, 시간 초과가 납니다.
• 이전 위상 문제와 다르게, 그래프의 간선을 저장하는 방식을 사용하였음에도 시간 초과가 났습니다. 우선 입출력 갯수가 10만개이기 때문에, 시간초과가 났을 것이라고 추론해볼 수 있겠습니다. 해서 cin, cout 방식의 입출력 방식을 사용하지 않고, 전통적인 printf, scanf를 사용해보도록 시도하였으나 결론은 시간초과.
• 해서 전통적인 방식의 bfs로 돌아가도록 합니다.

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
#define INF 987654321
using namespace std;


int n, k;
vector<int> cost;
vector<int> visited;
vector<vector<int>> graph;
vector<int> indegree;

int dfs(int idx) {
    if (visited[idx])
        return visited[idx];
    if (!indegree[idx]) {
        visited[idx] = cost[idx];
        return visited[idx];
    }
    visited[idx] = 0;
    for (int bf = 0; bf < graph[idx].size(); bf++) {
        int before = graph[idx][bf];
        visited[idx] = max(cost[idx] + dfs(before), visited[idx]);
    }
    return visited[idx];
}

int main(void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T; cin >> T;
    while (T--) {
        cin >> n >> k;
        cost = vector<int>(n + 1);
        visited = vector<int>(n + 1, 0);
        graph = vector<vector<int>>(n + 1);
        indegree = vector<int>(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            cin >> cost[i];
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            indegree[b] += 1;
        }

        int w; cin >> w;

        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (!indegree[i]) {
                visited[i] = cost[i];
                q.push(i);
            }        
        }

        while (!q.empty()) {
            int cur = q.front(); q.pop();

            for (int dir = 0; dir < graph[cur].size(); dir++) {
                int next = graph[cur][dir];

                indegree[next]--;
                if (visited[next] < visited[cur] + cost[next])
                    visited[next] = visited[cur] + cost[next];
                if (!indegree[next])
                    q.push(next);
            }
        }

        int res = visited[w];
        cout << res << endl;


    }



    return 0;
}

• 위의 dfs가 바로 기존 방식(시간 초과), 아래 queue를 이용한 방법이 새로 작성한 bfs로 해결하는 방식입니다.
• 아래의 경우 AC가 되었고, 이를 토대로 결론적으로 bfs로 풀이하는 것이 더 맞는 것 같습니다(저에게는)
• dfs에서 indegree를 제대로 활용하지 못한 점도 큰 것 같습니다. 역할이 겹쳐가.....