[GOLD3] ACM Craft

1. 문제 링크

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

---

2. 문제 이해 및 풀이 전략

위상 정렬 숙달을 위해 풀어본 첫 번째 문제.

처음 풀어본 줄 다리기 문제의 풀이법에 더해 '건설 시간'이라는 조건이 하나 더 붙었다.

조건의 추가와는 별개로 풀이의 핵심을 생각해보자면 다음 단계에 해당하는 노드로 진행하기 위해서는 같은 건설 단계의 노드 중 가장 긴 건설시간을 쓰는 노드의 시간이 그 단계의 소요 시간이 된다는 말이다.

그렇게 각 단계의 소요 건설 시간을 계산해본다.

 

* 2차 시도

각 단계의 시간을 계산하는 도중 건설 목표에 도달한 후 최소 시간을 저장하지 않고 지금까지 거친 시간을 출력하는 점을 개선해야했다.

메모이제이션을 사용해 각 지점에서 최소 시간을 저장하고, 단계를 넘기면 최장 시간을 넘긴다.    

---

3.  풀이 코드

int T;
int N, K;
int W;

int main()
{
    fastio;

	cin >> T;

    while (T--) 
    {
        cin >> N >> K;

        vector<int> Time;                             // 건설 시간
        vector<int> Degree(N + 1, 0);       // 차수 백터
        vector<vector<int>> Building(N + 1);    // 건물 그래프
        vector<int> Result(N + 1, 0);       // 최소 시간 저장 메모이제이션

        // 건설 시간 입력
        Time.push_back(0);              // 번호 맞추기
        for (int i = 1; i <= N; i++) 
        {
            int value;
            cin >> value;

            Time.push_back(value);
        }

        // 건물 그래프, 차수 입력
        for (int i = 0; i < K; i++)
        {
            int X, Y;
            cin >> X >> Y;

            Building[X].push_back(Y);
            Degree[Y]++;
        }

        // 최종 목적지 건물 입력
        cin >> W;


        // 위상 정렬 시작
        queue<int> q;
        // 진입 차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= N; i++) 
        {
            if (Degree[i] == 0) 
            {
                q.push(i);
                Result[i] = Time[i]; // 초기 건물 시간 저장
            }
        }

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

            for (int i = 0; i < Building[current].size(); i++) 
            {
                int next = Building[current][i];
                Result[next] = max(Result[next], Result[current] + Time[next]); //  최소 시간 갱신
                Degree[next]--;

                if (Degree[next] == 0) 
                    q.push(next);
            }
        }

        cout << Result[W] << '\n'; 
    }
    return 0;
}

---

4. 결과 및 회고

 

알고리즘의 적당한 예시로 보여줄만한 문제가 끝나면 어김없이 등장하는 다른 알고리즘과 함께 사용해야 하는 문제...라고 생각했다. 사실 각 노드의 최소시간을 저장해 놓는다는 생각이 나온 것은 문제를 잡고 꽤 오랜시간이 지난 후.