양효원

🏸

문제

정점 n(\(2 \le n \le 1000\)), 간선 k(\(1 \le k \le 100000\))개와 목표 정점 w가 주어진다.
아래 조건을 만족하며 w를 건설하기 위한 최소 시간을 구해야 한다.

  • 각 정점을 건설할 때의 시간은 d[n]로 주어진다.
  • 간선은 s e의 형태로 주어진다.
    • 간선 s e의 의미는 정점 s를 건설해야만 정점 e를 건설할 수 있다는 것이다.
    • 1 2, 3 2 간선이 있다면, 1과 3을 모두 건설해야 2를 건설할 수 있다.

풀이

  • 처음에는 top-down 방식으로 BFS를 사용하여 통과했다. 이후 찾아보면서 DFS+DP, 위상정렬 등의 풀이 또한 구현했다. 순서대로 소개하겠다.

top-down 방식의 BFS

  • 간선 정보를 뒤집어서 저장하고, w 노드부터 건설하며 최대 시간을 계산했다.
  • vis[n]을 사용하여 기존 시간보다 큰 경우에만 큐에 push한다.
BFS 코드 
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

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// top-down(AC)
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t, n, k, w;
    vector<long long> ans;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        vector<long long> d(n), vis(n, 0);
        vector<vector<int>> adj(n, vector<int>()), radj(n, vector<int>());
        for (int i = 0; i < n; i++) cin >> d[i];
        for (int i = 0; i < k; i++) {
            int s, e;
            cin >> s >> e;
            s--, e--;
            adj[s].push_back(e);
            radj[e].push_back(s);
        }
        cin >> w;
        w--;
        queue<long long> q;
        vis[w] = d[w];
        for (int i = 0; i < radj[w].size(); i++) {
            q.push((d[w] + d[radj[w][i]]) * 1000 + radj[w][i]);
            vis[radj[w][i]] = d[w] + d[radj[w][i]];
        }
        while (!q.empty()) {
            long long curi = q.front() % 1000, curt = q.front() / 1000;
            q.pop();
            for (int i = 0; i < radj[curi].size(); i++) {
                long long ni = radj[curi][i], nw = curt + d[radj[curi][i]];
                if (vis[ni] < nw) {
                    q.push(nw * 1000 + ni);
                    vis[ni] = nw;
                }
            }
        }
        long long cans = 0;
        for (int i = 0; i < vis.size(); i++) {
            if (cans < vis[i]) cans = vis[i];
        }
        ans.push_back(cans);
    }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
    return 0;
}

top-down 방식의 DFS + DP

  • BFS와 비슷하게 간선을 뒤집고, w 노드부터 건설하며 시간을 계산했다.
    • 각 노드에 대한 건설 시간을 dfs()로 호출하는 과정에서, memoization을 사용하여 중복 호출을 방지한다.
DFS + DP 코드 
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

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// dfs(top-down) + dp
int t, n, k, w;
vector<int> d;
vector<long long> dp;
vector<vector<int>> adj;
long long dfs(int ti) {
    if (dp[ti] != -1) return dp[ti];
    long long res = d[ti];
    for (int i = 0; i < adj[ti].size(); i++) {
        int ci = adj[ti][i];
        if (dp[ci] != -1) {
            if (res < dp[ci] + d[ti]) res = dp[ci] + d[ti];
        } else {
            if (res < dfs(ci) + d[ti]) res = dfs(ci) + d[ti];
        }
    }
    return dp[ti] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    vector<int> ans;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        d = vector<int>(n);
        dp = vector<long long>(n, -1);
        adj = vector<vector<int>>(n, vector<int>());
        for (int i = 0; i < n; i++) cin >> d[i];
        for (int i = 0; i < k; i++) {
            int s, e;
            cin >> s >> e;
            s--, e--;
            adj[e].push_back(s);
        }
        cin >> w;
        w--;
        ans.push_back(dfs(w));
    }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
    return 0;
}

Topological sort

  • 먼저 건설해야 하는 순서대로 노드를 위상 정렬한 후, w가 나올 때까지 건설 시간을 계산한다.
    • 위상 정렬은 BFS를 사용하였다.
Topological sort 코드 
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
67

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// tp sort
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t, n, k, w;
    vector<long long> ans;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        vector<int> d(n), ind(n, 0), tp, td;
        vector<long long> vis(n, 0);
        vector<vector<int>> adj(n, vector<int>());
        queue<int> q;
        for (int i = 0; i < n; i++) cin >> d[i];
        for (int i = 0; i < k; i++) {
            int s, e;
            cin >> s >> e;
            s--, e--;
            adj[s].push_back(e);
            ind[e]++;
        }
        cin >> w;
        w--;
        for (int i = 0; i < n; i++) {
            if (ind[i] == 0) {
                q.push(i);
                vis[i] = 1;
            }
        }
        td = d;
        while (!q.empty()) {
            int ci = q.front();
            tp.push_back(ci);
            q.pop();
            for (int i = 0; i < adj[ci].size(); i++) {
                int ni = adj[ci][i];
                ind[ni]--;
                if (vis[ni] == 0 && ind[ni] == 0) {
                    q.push(ni);
                    vis[ni] = 1;
                }
            }
        }
        vis = vector<long long>(n, -1);
        for (int i = 0; i < n; i++) vis[i] = d[i];
        for (int i = 0; i < n; i++) {
            int ci = tp[i];
            if (ci == w) break;
            for (int j = 0; j < adj[ci].size(); j++) {
                int ni = adj[ci][j];
                if (vis[ni] < vis[ci] + d[ni]) vis[ni] = vis[ci] + d[ni];
            }
        }
        if (vis[w] == -1)
            ans.push_back(d[w]);
        else
            ans.push_back(vis[w]);
    }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
    return 0;
}

풀고나서

  • 총 4가지 방법을 시도했다.
    1. BFS(top-down)
    2. BFS(bottom-up)
    3. DFS(top-down) + DP
    4. Topological sort
방법 BFS(top-down) BFS(bottom-up) DFS(top-down) + DP Topological sort
시간복잡도 \(O(K^{2}/4)\) \(O(K^{2}/4)\) \(O(N+K)\) \(O(N+K)\)
결과 804ms TLE 140ms 140ms
  • 2번을 뺀 나머지 방법들은 모두 AC되었지만, 아래와 같은 의문점이 남았다.
    • 1번도 시간복잡도상으로는 TLE가 나야 정상인데 왜 AC인지
      • 2번은 모든 리프 노드를 포함해서 시간이 더 걸린다는 차이점이 존재한다.
    • 3, 4번째 방법들은 시간복잡도는 같지만, 이론적으로 위상 정렬이 탐색하는 노드가 훨씬 적기 때문에 시간 차이가 있을 것 같은데, 어떻게 둘의 실행 시같이 같은지
  • TC 수가 적은 것이 원인이라고 추측된다.
    • 그렇다기엔 문제 번호가 1005라, TC도 충분할 것 같아서 찜찜함이 가시진 않는다.

Leave a comment

You may also enjoy

C++의 메모리 관리

Java에서는 다양한 gc 알고리즘을 통해 heap 영역의 메모리가 관리된다. 따라서 사용자가 메모리 release 과정을 신경쓸 필요가 없다. 하지만 C++의 경우, new 키워드 또는 malloc 함수를 통해 heap에 할당한 메모리는 직접 해제해야 한다. 이 내용을 포함하여...

BOJ 1477 - 휴게소 세우기

문제 기존 정점 n(\(0 \le n \le 50\)), 추가하는 정점 m(\(1 \le m \le 100\)), 선분의 길이 l(\(100 \le l \le 1000\))이 주어질 때, 아래 조건에 맞춰 정점 간의 거리의 최댓값의 하한을 구해야 한다. \(n+m \lt l...

구름LEVEL - 금은보화

문제 원소의 크기가 [1, 2000]에 속하는 정수이고, 길이가 \(N(1 \le N \le 250)\)인 수열 A가 주어진다. 위 수열을 두 개의 부분 수열 C, D로 나눌 때, 아래의 조건을 만족하는 C의 원소의 합 - D의 원소의 합의 차이의 최솟값과, 그 경우의 수를 구...

프로그래머스 - 마법의 엘리베이터

문제 현재 층수 \(L(1 \le L \le 100,000,000)\)과 절댓값이 \(10^{c}(c\ge 0, c \in \mathbb{N})\)인 엘리베이터 버튼이 주어질 때, 0층으로 갈 수 있는 경우의 수 중 버튼을 가장 적게 누르는 경우를 찾아야 한다. 음수 층으로는 갈...