본문 바로가기
개발/알고리즘

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

by JeonJaewon 2020. 2. 6.

이 문제에서 배웠던 것은 그래프 문제에서 시작 지점을 찾기가 애매할 경우 오히려 도착 지점을 시작 지점으로 선택하는 방법도 있다는 점.

왜냐? 도착 지점은 항상 정해져 있기 때문에 어디서 끝날지 조건만 확실하게 정해주면 된다!

(물론 간선의 방향은 초기화시 반대로 설정해야 한다)

 

그 후 재귀를 이용한 DFS로 풀었다. Node의 prevSum 변수로 직전 노드까지 경로의 weight들의 합을 계산하여, 여러번 계산함으로써 오는 성능 저하 문제를 해결하려고 했다.

 

또한 BFS는 그래프가 트리 구조가 확실하고, 회전하는 구조가 아닐 때 사용하는 것이 좋다. 이 문제의 경우도 BFS로 풀게 되면 각 노드들의 레벨을 따져주어야 하는 점이 골치아파진다. 이럴땐 DFS를 쓰자!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
using namespace std// notice vector is in std
 
class Node {
public:
    int weight;
    int prevSum;
    vector<int> nextNodes;
    Node() {
        prevSum = -1;
        weight = 0;
    }
};
Node* buildings;
int getTime(int index) {
    int tmp = 0;
 
    for (int i = 0; i < buildings[index].nextNodes.size(); i++) {
 
        int linkedIndex = buildings[index].nextNodes[i];
 
        if (buildings[linkedIndex].prevSum == -1) {
            int time = getTime(linkedIndex);
            tmp = time > tmp ? time : tmp;
        }
        else {
            if(tmp < buildings[linkedIndex].prevSum + buildings[linkedIndex].weight)
            tmp = buildings[linkedIndex].prevSum + buildings[linkedIndex].weight;
        } 
    }
 
    buildings[index].prevSum = tmp;
    if (buildings[index].nextNodes.size() == 0)
        return buildings[index].weight;
    return buildings[index].prevSum + buildings[index].weight;
    
}
int main() {
    int T, N, K;
    cin >> T;
    while (T > 0) {
        cin >> N >> K; //건물 개수, 건물 규칙 개수
        buildings = new Node[N + 1];
        for (int i = 1; i < N + 1; i++) {
            cin >> buildings[i].weight;
        }
        for (int i = 0; i < K; i++) {
            int to, from;
            cin >> to >> from;
            buildings[from].nextNodes.push_back(to);
        }
        int target;
        cin >> target;
 
        int curIndex = 0;
        int a = getTime(target);
        cout << a << endl;
 
        T--;
        delete[] buildings;
    }
 
     
}
cs

댓글