백준 1005 ACM Craft

 

 

<링크>

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

 

<풀이_1>

아무생각없이 하면 틀리는 이유는, 내가 완벽하지 못한데 다른 노드들을 갱신할 때 쓰이기 때문이다.

...-> A -> C ->...

...-> B -> C ->...

이렇게 둘이 있을 때 

아직 A가 완벽하게 갱신이 안돼서 최댓값을 못알아냈는데 C에게 정보를 제공해버렸다고 치자.

근데 나중에 A로 가는 다른 경로를 찾아서 A가 갱신이되면 C도 바꿔줘야되고 그 뒤로 연관된 모든놈들을 다 바꿔야된다.

그래서 나중에 피똥쌀 수가 있다. 그럼 A를 믿을수있게끔 만들어주는 방법은 A로 가는 모든경로들을 다 보면된다.

노드의 차수를 이용한다.

내 이전에 오는 노드들을 다 봤을때, 그 때 비로소 내가 다른 노드들을 갱신하는데 사용될 수 있게끔 했다.

 

<소스코드>

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
vector<int> adj[1001];
queue<int> q;
int time[1001];
int degree[1001];
int dp[1001];
int W;
void bfs();
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        memset(degree, 0, sizeof(degree));
        q = queue<int>();
        for (int i = 1; i <= 1000; ++i)
            adj[i] = vector<int>();
        int N, M;
        scanf("%d%d", &N, &M);
        for(int i=1;i<=N;++i)
            scanf("%d", time + i);
        while (M--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[a].push_back(b);
            ++degree[b];
        }
        scanf("%d", &W);
 
        for (int i = 1; i <= N; ++i)
            if (degree[i] == 0)
            {
                q.push(i);
                dp[i] = time[i];
            }
        bfs();
        printf("%d\n", dp[W]);
    }
}
void bfs()
{
    while (degree[W] != 0)
    {
        int cur = q.front();
        q.pop();
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int to=adj[cur][i];
            dp[to] = max(dp[cur] + time[to], dp[to]);
            --degree[to];
            if (degree[to] == 0)
                q.push(to);
        }
    }
}

<풀이_2>

목적지 W를 시작점으로 거꾸로 dfs하면 된다.

입력 받을때도 인접리스트를 싹다 거꾸로 받아주면 역방향 그래프가 완성된다.

연결리스트가 없는 끝노드까지 가면 걔는 시작건물이니깐 그냥 자기건물시간만 리턴해준다.

불필요한 재귀를 줄이기 위해 memozation을 사용했다.

<소스코드>

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[1001];
int t[1001];
vector<int> adj[1001];
int solve(int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, -1, sizeof(dp));
        for (int i = 1; i <= 1000; ++i)
            adj[i].clear();
        int N, M;
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i)
            scanf("%d", t + i);
        while (M--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[b].push_back(a);
        }
        int W;
        scanf("%d", &W);
        printf("%d\n",solve(W));
    }
}
int solve(int i)
{
    int &ret = dp[i];
    if (ret != -1)
        return ret;
    int m = 0;
    for (int to : adj[i])
        m = max(m, solve(to));
    return ret = m + t[i];
}