백준 4013번: ATM (C++)

접근

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

4013번: ATM

문제 해결을 위하여 Disjoint Set(Union Find) 알고리즘, 강한 연결 요소(SCC, Strongly Connected Component), 그리고 dp를 이용한 bfs 알고리즘을 이용하였다.

SCC는 방향이 있는 그래프에서 정점들이 서로 왕복 가능한 최대 크기의 집합을 구하는 알고리즘이다. A에서 B로, B에서 C로 왕복이 가능하다면 A, B, C 는 SCC 라고 할 수 있다. 이 문제에서 SCC 를 이용하는 이유는 중복 계산을 제거하기 위함이다. 이미 왔던 교차로를 재방문할 수 있다는 문제의 조건 하에서 서로 SCC인 교차로들 사이에서는 자유롭게 이동할 수 있다. 때문에 서로 자유롭게 이동할 수 있는 교차로들을 대표 교차로 1개로 묶어 계산한다면 쉽게 중복을 제거할 수 있다.

이 교차로들을 묶는 과정에서 Disjoint Set 알고리즘을 이용하게 된다. 대표 교차로 1개를 부모 노드로 지정하고, 해당 SCC 내에 있는 현금 보유량을 모두 합하고 레스토랑의 유무 또한 부모 노드에 저장해준다. 또한 자식 노드에 연결된 도로들도 부모노드로 옮겨주고 중복을 제거한다.

이렇게 만들어진 그래프는 사이클이 없는(사이클은 모두 SCC로 묶였기 때문에) 방향이 있는 그래프가 된다. 이 그래프의 시작점으로부터 dp 배열에 현재 교차로까지 방문했을 때 현금 인출량을 저장해주면서 bfs 알고리즘으로 탐색하며, 현재 노드에 레스토랑이 있을 때마다 현금 인출량을 ans 변수에 최대값을 갱신해준다면 탐색이 완료되었을 때 현금 인출량의 최대값을 구할 수 있다.

코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 500002

// Input
int N, M, S, P;
vector<int> Path[MAX_N];
int Cash[MAX_N];
int Restaurant[MAX_N];
// SCC
int id_arr[MAX_N];
int scc_finished[MAX_N];
stack<int> scc_stack;
int id;
// Disjoint Set
int Parent[MAX_N];
set<int> TPath[MAX_N];
// DP
set<int> ParentsSet;
int dp[MAX_N];

// Disjoint Set 알고리즘을 이용하여 같은 SCC로 묶인 교차로들을 한개의 대표 교차로로 묶어준다.
int Find(int x) {
    if (Parent[x] == x) return x;
    return (Parent[x] = Find(Parent[x]));
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        Parent[y] = x;
    }
}

// SCC 를 찾는 알고리즘을 이용하여 SCC 끼리 Union 을 해주고 한개의 대표 교차로로 묶어준다.
int dfs(int c) {
    id_arr[c] = ++id;
    scc_stack.push(c);
    int res = id_arr[c];
    for (int next : Path[c]) {
        if (id_arr[next] == 0) {
            res = min(res, dfs(next));
        } else if (!scc_finished[next]) {
            res = min(res, id_arr[next]);
        }
    }
    if (res == id_arr[c]) {
        // 같은 SCC끼리 Union하여 대표 교차로 묶고, 레스토랑의 유무, 현금 보유량도 모두 대표 교차로에 더해준다.
        while (1) {
            int t = scc_stack.top();
            scc_stack.pop();
            scc_finished[t] = 1;
            if (t == c) break;
            if (Restaurant[t]) Restaurant[c] = 1;
            Union(c, t);
            Cash[c] += Cash[t];
        }
        // 대표 교차로 1개를 BFS를 위한 교차로 목록에 추가해준다.
        ParentsSet.insert(c);
    }
    return res;
}

int Solve() {
    // Union-Find 를 위한 배열 초기화
    for (int i = 1; i <= N; i++) {
        Parent[i] = i;
    }
    // SCC 탐색하여 같은 SCC 끼리 Union 하면서 레스토랑의 유무, 현금 보유량도 대표 교차로에 추가
    for (int i = 1; i <= N; i++) {
        if (id_arr[i] == 0) dfs(i);
    }
    // 유니언한 교차로들을 대표 교차로로 묶은 후, 중복되는 도로를 제거
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < Path[i].size(); j++) {
            int a = Find(i);
            int b = Find(Path[i][j]);
            if (a != b && !TPath[a].count(b)) {
                TPath[a].insert(b);
            }
        }
    }
    // BFS를 진행하면서 최대 현금 인출량 체크
    int ans = 0;
    S = Find(S);
    queue<int> Q;
    Q.push(S);
    dp[S] = Cash[S];
    if (Restaurant[Find(S)]) ans = dp[Find(S)];
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int next : TPath[now]) {
            // 현재 위치에서 갈 수 있는 다음 위치 중, 현재 dp 현금 보유량 + 다음 ATM 현금 보유량 > 다음 dp 현금 보유량 일때만 탐색을 진행한다.
            if (dp[next] < dp[now] + Cash[next]) {
                dp[next] = dp[now] + Cash[next];
                // 다음 위치에 레스토랑이 있으면 ans의 최대값을 갱신한다
                if (Restaurant[next]) ans = max(ans, dp[next]);
                Q.push(next);
            }
        }
    }
    return ans;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        Path[a].push_back(b);
    }
    for (int i = 1; i <= N; i++) {
        cin >> Cash[i];
    }
    cin >> S >> P;
    for (int i = 0; i < P; i++) {
        cin >> a;
        Restaurant[a] = 1;
    }

    cout << Solve() << endl;

    return 0;
}

더 생각해 볼 것?

이전에 파이썬으로 풀다가 포기한 기억이 난다. 이번에 C++ 로 다시 풀면서 풀게되어 감회가 새롭다. 앞으로도 더 열심히 해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!