[ BOJ 백준 11097번 - 도시 계획 ] 해설 및 코드

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

 

목적

방향 그래프의 인접 행렬이 주어졌을 때, 간선의 개수를 최소로 만들자.

 

접근법

1. 사이클을 형성하는 부분 그래프 단위로 보면 쉽다. 만약 n개의 정점들이 사이클을 형성한다면, 최소 간선의 개수는 n개일 것이다. 그리고 임의의 두 사이클 간에 이동이 가능하다면 간선은 한개만 추가하면 될 것이다.

 

2. 즉, SCC로 이루어진 서브 그래프들을 구하고 그러한 서브 그래프간의 연결이 있는지 확인하면 된다. 코사라주 알고리즘을 사용하면 SCC는 쉽게 구할 수 있을 것이다.

 

3. SCC간의 연결은 코사라주 알고리즘 과정에서 만든 스택 데이터를 사용한다. 이 데이터는 정점의 방문 완료시간 순으로 스택에 쌓이기 때문에 가장 나중에 삽입된 정점은 먼저 삽입된 정점들로 가는 경로가 있을 수도 없을 수도 있다. 하지만 먼저 삽입된 정점에서 나중에 삽입된 정점으로 가는 경로는 존재하지 않는다. (코사라주 알고리즘을 정확히 이해해야 한다.)

4. 정점을 추가한 그래프에서 코사라주 알고리즘을 수행하면 오른쪽과 같이 스택에 데이터가 쌓일 것이다. 주목할 것은 1번 정정과 2번 정점 사이의 간선이다. 1에서 2로는 7을 거쳐서 갈 수 있기 때문에 1과 2를 연결하는 간선은 없애야한다.

 

5. 임의의 정점 a,b에 대해 p[a][b]가 a에서 b로 가는 경로가 있는지를 나타낼 때, 정점 i와 정점 j 사이에 임의의 정점 k에 대해 p[i][k] && p[k][j] 를 만족한다면 i에서 j로 가는 간선은 포함시키면 안된다. 이때 k의 범위는 위 그림의 스택 데이터 중 검사하려는 두 정점 사이에 있는 정점들이다. 즉 1에서 2로가는 간선을 답으로 포함할 지는 k의 범위를 초록색으로 표시한 정점들로 하여 확인하면 될 것이다. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
 
const int MAXN=301;
char tmp[MAXN];
int n,cnt,no,s[MAXN];
bool edge[MAXN][MAXN],redge[MAXN][MAXN],vis[MAXN],used[MAXN][MAXN];
 
 
void dfs(int u,bool ed[][MAXN], vi& list){
    vis[u]=true;
    f(i,1,n)if(ed[u][i]&&!vis[i])dfs(i,ed,list);
    list.push_back(u);
    s[u]=no;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;cin>>t;
    while(t--){
        cin>>n;
        f(i,1,n){
            cin>>tmp;
            f(j,1,n){
                edge[i][j]=(i==j?false:(tmp[j-1]=='1'));
                redge[j][i]=edge[i][j];
            }
        }
        
        vi p;
        memset(vis,false,n+1);
        f(i,1,n)if(!vis[i])dfs(i, edge, p);
        
        vvi scc;
        cnt=no=0;
        memset(vis,false,n+1);
        fr(i,n-1,0)if(!vis[p[i]]){
            vi list;
            dfs(p[i], redge, list);
            ++no;
            scc.push_back(list);
            if(list.size()>1)
                cnt+=list.size();
        }
        
        vvi ans;
        memset(used,false,sizeof(used));
        fr(i,n-1,1)fr(j,i-1,0){
            int u=p[i],v=p[j];
            if(!edge[u][v]||used[s[u]][s[v]]||s[u]==s[v])continue;
            bool poss=true;
            fr(k,i-1,j+1)if(edge[u][p[k]]&&edge[p[k]][v]){
                poss=false;
                break;
            }
            if(poss){
                used[s[u]][s[v]]=true;
                ans.push_back({u,v});
            }
        }
        
        cout<<cnt+ans.size()<<'\n';
        for(vi &list:scc)if(list.size()>1){
            int u=list[list.size()-1];
            for(int &v:list){
                cout<<u<<' '<<v<<'\n';
                u=v;
            }
        }
        for(vi &ed:ans)cout<<ed[0]<<' '<<ed[1]<<'\n';
    }
    return 0;
}
 

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

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