[ BOJ 백준 2152번 - 여행 계획 세우기 ] 해설 및 코드

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

 

목적

단방향인 비행기 경로가 m개 주어질 때,  S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하자.

 

접근법

1. SCC이론과 연관되어 있는 문제이다. 

 

2. SCC를 하나의 정점이라고 하고 이러한 정점의 가중치를 요소의 개수로 가정할 수 있다. 이 때, S번 도시가 포함된 정점에서 T번 도시가 포함된 정점으로 가는 경로의 최대값을 구하면 된다.

 

3. 우선, 코사라주 알고리즘으로 SCC를 구한다. 정점마다 자신이 속해있는 SCC의 번호를 할당하고, 각 SCC의 요소 개수를 구하자.

 

4. SCC를 정점으로 하는 간선을 구하고, 이를 이용하여 BFS로 최대 경로를 구한다. (BFS에서 메모리 초과를 방지하기 위해 이전 갱신 값보다 큰 경우만 큐에 삽입하자.)

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int MAXN=1e4+1;
vector<int>    edge[MAXN],edge_rev[MAXN];
set<int> edge_scc[MAXN];
int n,m,s,t,idx,order[MAXN],scc[MAXN],cnt[MAXN],vis[MAXN];
 
void sort(int u){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])sort(v);
    order[idx--]=u;
}
 
int findSCC(int u){
    int ret=1;
    vis[u]=true;
    for(int &v:edge_rev[u])if(!vis[v])ret+=findSCC(v);
    scc[u]=idx;
    return ret;
}
 
int bfs(){
    int ans=0;
    queue<pair<int,int>> q;
    q.push({s,cnt[s]});
    memset(vis, 0, 4*(idx+1));
    while(!q.empty()){
        int i=q.front().first,sum=q.front().second;
        q.pop();
        if(i==t)ans=max(ans,sum);
        else {
            for(auto j:edge_scc[i])if(vis[j]<sum+cnt[j]){
                vis[j]=sum+cnt[j];
                q.push({j,vis[j]});
            }
        }
    }
    return ans;
}
 
int sol(){
    idx=n;
    f(i,1,n)if(!vis[i])sort(i);
    
    memset(vis, 0, 4*(n+1));
    f(i,1,n)if(!vis[order[i]]){
        ++idx;
        cnt[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]);
    s=scc[s];
    t=scc[t];
    
    return bfs();
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>s>>t;
    while(m--){
        int a,b;cin>>a>>b;
        edge[a].push_back(b);
        edge_rev[b].push_back(a);
    }
    cout<<sol();
}
 

 

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

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