BOJ 11097번 도시 계획

1<= N <= 300

문제를 간단하게 말하자면,

방향 그래프가 있고 (흔히 플로이드로 O(N^3)에 많이 구하는)그래프의 각 정점간의 이동 가능성에대한 2차원 테이블이 주어질 때 이 테이블을 만족하는 그래프들 중 간선의 수가 최소인 그래프를 찾아서 그 간선의 수와 간선들을 출력하는 문제이다.

우선 이 테이블을 바탕으로 방향 그래프를 만들어보자. 그럼 분명 이 그래프에 대해서 플로이드를 돌려 테이블을 만들어도 주어진 테이블이 나올 것이다. 하지만 최소한의 간선이 아니다. 왜냐하면 필요없는 간선들이 있기 때문이다. 예를 들어 a->b, b->c, a->c 가 연결 되어있다면 a->c 가 없어도 a에서 b를 통해 c로 갈 수 있기 때문에 a->c 는 필요 없는 간선이 된다.

아무튼 이런 쓸모없는 간선들을 찾아서 지워주는게 문제의 핵심인데, 문제는 어떻게 해야하느냐이다.

우선 확실한건 같은 SCC내에 있는 노드 K개가 있다면 이 들이 SCC를 이루기 위한 최소한의 간선 수는 K개 이다. 이 것은 자명하다.

그리고 다른 SCC간의 간선은 딱 하나만 필요하므로 정점 압축을 한뒤 플로이드로 불필요한 간선을 지울 수가 있다. u -> k 이고 k -> v이면 u -> v 는 필요없다는 식으로 지울수있다.

그리고 SCC를 묶지않고 처음부터 플로이드로만 불필요한 간선을 지우면 되지않을까해서 새로 짜봤는데 틀렸는데, 생각을 좀 해보면. 같은 SCC 내에 K개의 정점이 있다면 이 정점들 간의 간선은 딱 K개만 있으면 되는데 플로이드로만하면 K개보다 많은 개수의 간선이 남아있을 수도 있기때문에 최소 간선을 구하라는 문제에 대한 답이 될 수가 없다. 예외의 예를 들자면 1->2, 2->3, 3->4, 4->5, 5->1 에서 3->1 을 그어도 플로이드만으로는 3->1은 지워지지않는다 하지만 같은 SCC내에 있기 때문에 사실상 불필요하다. 

※ 이 문제를 통해 플로이드로 할 수 있는 것을 추가적으로 세가지를 배웠다. 물론 N이 충분히 작아야하지만

1. 사이클이 있는지 없는지 간단하게 찾을 수가있음

all i adj[i][i] = 0 으로 주고 플로이드를 돌려서 all i adj[i][i] ==0 이어야 사이클이 없는것이고 하나라도 1이면 사이클이 있는것이다.

2. 플로이드를 돌린뒤 O(N^2) 로 SCC를 묶을 수가있음.(물론 플로이드돌리는데 걸리는시간 빼고) cango[i][j] == cango[j][i] 면 i와 j는 같은 scc이므로 union-find로 묶어도 되고, 간단하게 이중 for 문으로 묶을 수 있다. 코드는 이 문제 소스코드에 포함되어있음.

3. 불필요한 간선을 제거 할 수가있음. (위에서 설명했다.)

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int cango[303][303];
int sccId[303];
int N,T,sccCnt;
int adj[303][303];
vi sccMem[303];
int main() {
    inp1(T);
    while(T--){
        sccCnt=0;
        memset(sccId,-1,sizeof(sccId));
        memset(cango,0,sizeof(cango));
        memset(adj,0,sizeof(adj));
        FOR(i,303) sccMem[i].clear();
        getchar();
        inp1(N);
        FOR(i,N) FOR(j,N) scanf("%1d",&cango[i][j]);
        FOR(i,N){
            if(sccId[i]==-1) sccId[i] = sccCnt++, sccMem[sccId[i]].pb(i);
            for(int j = i+1; j < N; j++){
                if(sccId[j]!=-1) continue;
                if(cango[i][j] && cango[j][i]) sccId[j] = sccId[i], sccMem[sccId[j]].pb(j);
            }
        }
        
        FOR(i,N) FOR(j,N) if(cango[i][j] && sccId[i] != sccId[j]) adj[sccId[i]][sccId[j]] = 1;
        FOR(k,sccCnt){
            FOR(i,sccCnt){
                FOR(j,sccCnt){
                    if(adj[i][j] && adj[i][k] && adj[k][j]) adj[i][j]=0;
                }
            }
        }
        vii ans;
        FOR(i,sccCnt){
            if(sz(sccMem[i])<=1) continue;
            FOR(j,sz(sccMem[i])){
                ans.pb({sccMem[i][j],sccMem[i][(j+1)%sz(sccMem[i])]});
            }
        }
        FOR(i,sccCnt){
            FOR(j,sccCnt){
                if(adj[i][j]) ans.pb({sccMem[i][0],sccMem[j][0]});
            }
        }
        printf("%d\n",sz(ans));
        for(auto p : ans){
            printf("%d %d\n",p.first+1, p.second+1);
        }
        printf("\n");
    }
    return 0;
}