[ BOJ 백준 4013번 - ATM ] 해설 및 코드

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

 

 

 

목적

출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 구하자.

 

접근법

1. 백준 2152 - 여행 계획 세우기 와 유사한 문제이다. SCC를 응용한 문제이며, 코사라주 알고리즘과 BFS로 최대값을 구할 수 있다.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
typedef vector<int> vi;
typedef set<int> si;
 
const int MAXN=5e5+1;
int n,m,s,p,idx;
int money[MAXN],order[MAXN],vis[MAXN],scc[MAXN],totalMoney[MAXN];
bool restaurant[MAXN],hasRestaurant[MAXN];
vi edge[MAXN],edge_rev[MAXN];
si edge_scc[MAXN];
 
void findOrder(int u){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])findOrder(v);
    order[idx--]=u;
}
 
int findSCC(int u){
    int ret=money[u];
    vis[u]=true;
    for(int &v:edge_rev[u])if(!vis[v])ret+=findSCC(v);
    scc[u]=idx;
    if(restaurant[u])hasRestaurant[idx]=true;
    return ret;
}
 
int bfs(){
    memset(vis, 0, 4*(idx+1));
    int ret=0,i=scc[s];
    queue<int> q;q.push(i);
    vis[i]=totalMoney[i];
    while(!q.empty()){
        int i=q.front();q.pop();
        if(hasRestaurant[i])ret=max(ret,vis[i]);
        for(int j:edge_scc[i])if(vis[j]<vis[i]+totalMoney[j]){
            vis[j]=vis[i]+totalMoney[j];
            q.push(j);
        }
    }
    return ret;
}
 
int sol(){
    idx=n;
    f(i,1,n)if(!vis[i])findOrder(i);
    
    memset(vis, 0, 4*(n+1));
    f(i,1,n)if(!vis[order[i]]){
        ++idx;
        totalMoney[idx]=findSCC(order[i]);
    }
    
    f(i,1,n)for(int &v:edge[i])if(scc[i]!=scc[v])edge_scc[scc[i]].insert(scc[v]);
    
    return bfs();
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    while(m--){
        int a,b;cin>>a>>b;
        edge[a].push_back(b);
        edge_rev[b].push_back(a);
    }
    f(i,1,n)cin>>money[i];
    cin>>s>>p;
    f(i,1,p){
        int tmp;cin>>tmp;
        restaurant[tmp]=true;
    }
    
    cout<<sol();
    return 0;
}
 

 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.