[백준/C++] 1005번 ACM Craft

---

 

이 문제를 처음 봤을 때는 최단경로 (Shortest Path)문제라고 생각하였습니다.

그래서 맨 뒤에서부터 각 Tree Level마다 걸리는 최대 시간을 찾아 return하면 되겠다고 생각하였습니다.

 

주어지는 간선(edge)를 거꾸로 받아서 출발하는 간선이 없는 노드(vertax)를 도착점으로 하면 되겠다고 생각하였으나,

교차되거나 복잡하게 꼬여있는 곳에서 오류가 생긴다는 것을 알게 되었고 왜 사용하지 못하는가에 자세한 사항은 아래 링크를 넣겠습니다.

 

아래 링크에 bfs, dfs,다익스트라, 재귀 등등 중요한 꿀팁이 들어있습니다.

https://www.acmicpc.net/board/view/30959

글 읽기 - ★☆★☆★ [필독] ACM Craft FAQ ★☆★☆★

이 문제는 위상정렬과 다이나믹프로그래밍이 핵심인 문제이며

위상정렬을 통해 제가 처음에 고민했던 각 트리 레벨마다 구별을 할 수 있습니다.

---

#include <bits/stdc++.h>
#define SETTING ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std ;

int N, K, DEST;
int totalTime[1001] ;
int buildTime[1001] ;
int Topology_Sort[1001] ;
vector< vector <int> > graph(1001) ;

void find_answer()
{
    queue<int> que ;

    for(int i = 1 ; i <= N ; i++)
        if(!Topology_Sort[i]) que.push(i) ;
    
    while(!que.empty())
    {
        int curr = que.front() ;
        que.pop() ;

        if(curr == DEST) break ;
        for(int i = 0 ; i < graph[curr].size() ; i++)
        {
            totalTime[graph[curr][i]] = 
                max(totalTime[graph[curr][i]], totalTime[curr] + buildTime[curr]) ;
            
            Topology_Sort[graph[curr][i]]-- ;
            if(!Topology_Sort[graph[curr][i]]) que.push(graph[curr][i]) ;
        }
    }
}

void input_setting()
{
    int startPoint, endPoint ;
    graph = vector< vector <int> > (1001) ;

    memset(buildTime, 0, sizeof(int) * 1001) ;
    memset(totalTime, 0, sizeof(int) * 1001) ;
    memset(Topology_Sort, 0, sizeof(int) * 1001) ;
    
    cin >> N >> K ;
    for(int i = 1 ; i <= N ; i++)
        cin >> buildTime[i] ;
    
    for(int i = 0 ; i < K ; i++)
    {
        cin >> startPoint >> endPoint ;
        graph[startPoint].push_back(endPoint) ;
        Topology_Sort[endPoint]++ ;
    }

    cin >> DEST ;
}

int main()
{
    SETTING ;
    int T ;
    cin >> T ;
    for(int i = 0 ; i < T ; i++)
    {
        input_setting() ;
        find_answer() ;
        cout << totalTime[DEST] + buildTime[DEST] << "\n" ;
    }
}

---

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

1005번: ACM Craft