Problem Solving/BOJ

[백준 4013번] [SCC / Tree DP] ATM

  • -
728x90
반응형

일단, 그리디한 관점으로 보면 가능한 ATM 기기를 최대한 많이 거쳐가는 것이 유리하다.

하지만, 모든 ATM 기기를 전부 다 갈 수 없는데, 그 이유는 Directed graph이기 때문이다.

 

그런데, SCC에서는 위 문제가 완전히 해결된다.

SCC의 특성이 해당 컴포넌트 내부에서 임의의 두 노드를 잡았을 때 반드시 해당 두 노드를 연결하는 path가 존재한다는 것이다.

즉, SCC 내부에 존재하는 ATM은 전부 다 방문할 수 있게 된다.

 

또한 추가적으로 SCC를 만들게 되면 장점이 DAG가 만들어진다는 것이다.

이를 이용하여 Topological sorting을 할 수 있게 된다.

 

즉, SCC단위로 ATM기에 존재하는 금액의 총 합, 레스토랑 존재 여부를 다룰 수 있고

위 문제는 출발 지점이 속하는 SCC에서 레스토랑이 존재하는 SCC 들 중 금액의 최댓값을 구하는 문제로 변경되고

DAG이므로 DP를 통해 쉽게 구할 수 있다. (Shortest path에서 DAG가 보장되면 DP로 풀 수 있는 뉘앙스와 거의 유사하다.)

#include <bits/stdc++.h> #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair<int, int>; using tiii = tuple<int, int, int>; vector<int> edge[500001]; vector<int> scc_edge[500001]; vector<int> rest_list; stack<int> s; stack<int> topological_sort; int idx[500001]; int idx_low[500001]; int cash[500001]; int sccNum[500001]; int sccCash[500001]; bool sccRes[500001]; int sccMAX[500001]; int start; int rest_num; bool in_stack[500001]; bool rest[500001]; int visited[500001]; bool can[500001]; int cur_time = 0; int scc_num = 0; void dfs(int cur){ visited[cur] = 1; for(int i = 0; i < scc_edge[cur].size(); i++){ int next_node = scc_edge[cur][i]; if(visited[next_node] == 0){ dfs(next_node); } } topological_sort.push(cur); } void tarjan(int cur_node){ idx[cur_node] = idx_low[cur_node] = cur_time++; s.push(cur_node); in_stack[cur_node] = 1; for(int i = 0; i < edge[cur_node].size(); i++){ int next_node = edge[cur_node][i]; if(idx[next_node] == -1){ tarjan(next_node); idx_low[cur_node] = min(idx_low[cur_node], idx_low[next_node]); } else if(in_stack[next_node]){ idx_low[cur_node] = min(idx_low[cur_node], idx[next_node]); } } if(idx[cur_node] == idx_low[cur_node]){ int cur_scc_num = scc_num++; bool rest_check = false; int tmp; do{ tmp = s.top(); s.pop(); in_stack[tmp] = false; sccNum[tmp] = cur_scc_num; if(rest[tmp]) rest_check = true; sccCash[cur_scc_num] += cash[tmp]; }while(!s.empty() && tmp != cur_node); if(rest_check) sccRes[cur_scc_num] = true; sccMAX[cur_scc_num] = sccCash[cur_scc_num]; } } int main() { fastio; memset(sccCash, 0, sizeof(sccCash)); memset(sccRes, 0, sizeof(sccRes)); memset(idx, -1, sizeof(idx)); memset(idx_low, -1, sizeof(idx_low)); memset(in_stack, 0, sizeof(in_stack)); memset(rest, 0, sizeof(rest)); memset(visited, 0, sizeof(visited)); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; edge[a].push_back(b); } for(int i = 1; i <= n; i++){ int t; cin >> t; cash[i] = t; } cin >> start >> rest_num; for(int i = 0; i < rest_num; i++){ int t; cin >> t; rest[t] = 1; } for(int i = 1; i <= n; i++){ if(idx[i] == -1) tarjan(i); } start = sccNum[start]; for(int i = 1; i <= n; i++){ for(int j = 0; j < edge[i].size(); j++){ int next_node = edge[i][j]; if(sccNum[i] != sccNum[next_node]){ scc_edge[sccNum[i]].push_back(sccNum[next_node]); } } } for(int i = 0; i < scc_num; i++){ if(visited[i] == 0){ dfs(i); } } can[start] = 1; while(!topological_sort.empty()){ int cur = topological_sort.top(); topological_sort.pop(); if(can[cur] == 0) continue; for(int i = 0; i < scc_edge[cur].size(); i++){ int next_scc = scc_edge[cur][i]; can[next_scc] = 1; sccMAX[next_scc] = max(sccMAX[next_scc], sccMAX[cur] + sccCash[next_scc]); } } int result = 0; for(int i = 0; i < scc_num; i++){ if(can[i] && sccRes[i] && sccMAX[i] > result){ result = sccMAX[i]; } } cout << result << "\n"; return 0; }

 

반응형
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.