[백준/C++] 1005 ACM Craft

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

1005번: ACM Craft

 

[문제]

 

 

 

위 사진 처럼 그래프가 주어지고 N번 건물까지 짓는데 소요되는 시간이 주어진다. 

이 때, 4번과 같은 노드는 2번, 3번이 모두 지어져야 지을 수 있음. 

한 건물을 지으려면 간선이 연결된 모든 노드들이 지어져야 그 번호를 지을 수 있다.

 

=> 결국 한 건물을 지으려면 그 전의 건물을 다 지어야하기 때문에 그 전 건물 중 최장 시간을 가지게 되는 것이다.

빨간색을 목표지점이라 했을 때, 시작 지점(5가 적혀있는 지점)에서 가는 방법은 총 두가지 인데 

5->4->3->2 ( 총합 14)/ 5->3->2(총합 10) 

=> 이렇게 될 경우 정답은 14임. 

 

[풀이 과정]

일단 그래프기 때문에 2차원 배열을 만들자는 생각을 했음. -> vector<vector<int>> v

그리고 보고나서 바로 떠오른 풀이법은 DP, Dijkstra 정도... 근데 또 다익스트라는 감이 잘 안와서 

그냥 dp에 간선이니까 BFS 방식 채택해서 일단 해봤다.

단순한데 BFS를 그대로 사용하고, 저장된 시간보다 더 높은 값이면 다시 queue에다 넣어준다. >> 재 계산 

시작 점이 어딘지 모르겠어서 목표하는 점부터 거꾸로 구해줬다.

-> 나중에 보니까.. 들어오는 간선이 없는 점이 시작 정점인듯..??

#include<bits/stdc++.h>

using namespace std;

int T;
int DP[1001];//누적 시간 비교
int times[1001]; // 각 건물 짓는데 필요한 시간

void BFS(int W, int N, vector<vector<int>> node) {
	
    
	queue<int> q;
	q.push(W);
	
	int start = 0;
	
    //DP[W]에는 times[W]를 넣어준다. -> 시작점을 모르겠어서 거꾸로 진행
	DP[W] = times[W];
	
	while (!q.empty()) {
		start = q.front();
		q.pop();
		for (int i = 0; i < node[start].size(); i++) {
			if (node[start][i]) {
            	// 시작 정점까지의 누적 시간 + 도착 정점의 건설 시간 
                // 지금까지 측정한 최대 시간보다 크다면, 다시 측정.
				if (times[node[start][i]] + DP[start] > DP[node[start][i]]) {
					q.push(node[start][i]);
					DP[node[start][i]] = DP[start] + times[node[start][i]];
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	for (int t = 0; t < T; t++) {
		fill(DP, DP + 1001, 0);
		int N, K;
		cin >> N >> K; // 건물 개수, 건설 순서 규칙의 총 개수
		vector<vector<int>> node(N + 1);
		for (int i = 1; i <= N; i++) {
			cin >> times[i];
		}
		int start, end;

		for (int i = 0; i < K; i++) {
			cin >> start >> end;
			node[end].push_back(start); // 거꾸로
		}

		int W;
		cin >> W;

		BFS(W, N, node);

		sort(DP, DP + N+1,greater<int>());


		cout << DP[0] << '\n';
	}

}

 

 

[고찰]

처음에 마냥 2차원 배열로 해줬더니 시간초과가 나서 vector를 사용해줬다.

 

 

알고리즘 분류에 보면 위상정렬? 이라는게 있는데 처음봄...

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int main(){
    int N, time[500], result[500] = {0}, indegree[500] = {0};
    vector<int> adj[500];
    queue<int> Q;
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%d", time+i);
        while(1){
            int pre;
            scanf("%d", &pre);
            if(pre == -1) break;
            indegree[i]++;
            adj[pre-1].push_back(i);
        }
        // indegree = 0인 정점을 큐에 넣어 둠
        if(indegree[i] == 0){
            result[i] = time[i];
            Q.push(i);
        }
    }
 
    // 위상 정렬
    for(int i=0; i<N; i++){
        int curr = Q.front();
        Q.pop();
        for(int next: adj[curr]){
            // 최소 건설 완료 시간 갱신
            result[next] = max(result[next], result[curr]+time[next]);
            // 간선을 삭제하여 next의 indegree가 0이 되면 next도 큐에 넣음
            if(--indegree[next] == 0) Q.push(next);
        }
    }
 
    // 결과 출력
    for(int i=0; i<N; i++)
        printf("%d\n", result[i]);
}
[출처] 위상 정렬(Topological Sort) (수정: 2017-06-22)|작성자 라이

 

 

 

 

 

 

[위상정렬]

위상 정렬(Topological Sort) (수정: 2017-06-22)