BOJ 11097 - 도시계획

* BOJ 11097 도시계획 (https://www.acmicpc.net/problem/11097)

  [ 분류 - SCC(Strongly connected components) ]

  다소 까다로운 문제? 였다. 반면 접근 방식이 매우 여러가지라 아래 해설도 그 중 하나라고 봐주시면 되시겠당 :)

  문제가 물어보는 것은 플로이드의 결과라고 생각할 수 있는 인접 행렬이 주어졌을 때, 이를 구성할 수 있는 가장 적은 도로를 쓰는 도로망을 구성하는 것이다. 그리고 일방통행 도로이기 때문에 방향 그래프인 것을 알 수 있다.

  

  이 문제를 "최대한 도로를 지우는" 과정으로 볼 수 있다. 인접 행렬에서 지울 수 있는 도로를 모두 지워야 최소 크기의 도로망을 구성할 수 있기 때문이다.

  임의의 정점에 대해서 생각해보자. 정점 A에서 정점 B로 가는 A->B 도로가 있을 때, 삭제 판단을 해야한다고 가정해보자.

  만약 A에서 B로 가는 경로가 이 도로로 유일하다면 절대로 지울 수 없다. 지운다면 해당 인접 행렬 값에 0이 발생하기 때문이다. 그렇다면 A와 연결된 임의의 도시 X, 그리고 이 X가 B로 갈 수 있다면 A->B를 지울 수 있다. 따라서 아래처럼 결론을 낼 수 있다.

  ∴ A->X->B 라면 A->B는 삭제할 수 있다.

 

  하지만 이 명제는 A와 B가 사이클을 이룰 때 논리적으로 맞다고 할 수 없다. 재귀적으로 파고들기 때문인데, 이를 피하기 위해선 사이클을 이루는 정점들끼리 모아줄 필요가 있다. 가령 아래의 구성인 경우 A, B, C 모두 갈 수 있으나 결국인 필요한 도로의 수는 3개 밖에 되지 않는다.

  따라서 사이클을 이루는 정점에 대한 도로 설정과 사이클을 이루지 않는 정점에 대한 도로 설정을 달리 해줘야 한다.

  이를 위해 SCC 알고리즘을 사용해야 한다. 사이클을 이루는 정점 집합을 SCC로 묶어주고, SCC가 DAG이기 때문에 사이클을 이루지 않는 정점 처리를 여기서 해줘야 한다.

  - SCC 간의 도로 삭제 여부 판단

  우선 SCC 그래프는 DAG이기 때문에 위상 정렬이 가능하다. 따라서 판단을 이 순서에 따라 맞춰서 진행한다.

  

  현재 방문하는 SCC를 u라고 할 때, 자식들을 v1, v2, v3, ..., vn 이라고 하자. 그렇다면 u->v1을 지우기 위해서는 k=[2, n]에 대해 u->vk->v1이 하나 이상 있어야 한다. 사실 이 처리 때문에 머리 좀 썩혔는데, 새로운 인접 행렬을 그려서(주어진 인접 행렬은 도시 간의 인접 행렬이고 지금 만드려는 행렬은 SCC의 행렬), 자식들이 갈 수 있는 모든 SCC에 대해 각각 처리를 해주고 그 값을 합해주자. 

  이는 SCC 처리이기 때문에 처음엔 SCC X에서 SCC Y로 갈 수 있는 도로가 하나 이상이기 때문에 이를 "하나"로 보기 위해서 boolean으로 OR연산 해줘서 하나로 퉁쳐준다. X에서 Y로 가는 도로를 하나만 건설하면 되기 때문이다.

  그리고 이 더해준 것을 통해 vk로 갈 수 있는 경로를 O(1)로 알 수 있다. 만약 이 값이 1이라면 해당 SCC로 갈 수 있는 경우의 수는 단일 한 가지이기 때문이다.

  (이 과정은 좀 설명이 뭐같으므로 소스를 보길 추천합니당.. ㅠ)

이렇게 하면 사이클을 이루지 않는 SCC의 도로를 구성할 수 있다.

나머지는 사이클을 이루는 SCC 내부의 처리는 단순히 하나씩 이으며 원을 만들도록 구성해주면 최소가 된다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
int max_v(int a, int b) { return a > b ? a : b; }
struct _d { int u, v; };
const int MAX_V = 301;
char board[MAX_V][MAX_V];
int sccId[MAX_V], discovered[MAX_V], sccCount, discCount;
int N;
vector<vector<int>> sccs;
stack<int> stk;
int scc(int u) {
	int ret = discovered[u] = discCount;
	discCount++;
	stk.push(u);

	for (int v = 0; v<N; v++)
		if (board[u][v] - '0') {
			if (discovered[v] == -1)
				ret = min_v(ret, scc(v));
			else if (sccId[v] == -1)
				ret = min_v(ret, discovered[v]);
		}

	if (ret == discovered[u]) {
		sccs.push_back(vector<int>());
		while (1) {
			int t = stk.top(); stk.pop();
			sccId[t] = sccCount;
			sccs[sccCount].push_back(t);
			if (t == u) break;
		}
		sccCount++;
	}
	return ret;
}

int main() {
	int T, i, j, m, ind[MAX_V], outd[MAX_V], u,v, dummy[MAX_V],dummy2[MAX_V],sz;
	set<int> sccadj[MAX_V];
	vector<_d> ans;
	scanf("%d\n", &T);
	while (T--) {
		scanf("%d\n", &N);
		for (i = 0; i < N; i++) {
			scanf("%s", board[i]);
			sccadj[i].clear();
		}

		sccs.clear(); sccs.resize(0);
		memset(sccId, -1, sizeof sccId);
		memset(discovered, -1, sizeof discovered);
		sccCount = discCount = 0;
		for (i = 0; i < N; i++)
			if (discovered[i] == -1) scc(i);

		memset(ind, 0, sizeof ind);
		for (i = 0; i < N; i++)
			for (j = 0; j < N; j++)
				if (board[i][j] - '0' && sccId[i] != sccId[j]) {
					if (sccadj[sccId[i]].find(sccId[j]) == sccadj[sccId[i]].end()) {
						sccadj[sccId[i]].insert(sccId[j]);
						ind[sccId[j]]++;
					}
				}

		queue<int> q;
		for (i = 0; i < sccCount; i++)
			if (!ind[i]) q.push(i);
		
		ans.clear();
		ans.resize(0);
		while (!q.empty()) {
			u = q.front(), q.pop();
			memset(dummy, 0, sizeof(int)*sccCount);
			for (auto it = sccadj[u].begin(); it != sccadj[u].end(); it++) {
				v = *it;
				memset(dummy2, 0, sizeof(int)*sccCount);
				for (int& s : sccs[v]) {
					for (i = 0; i < N; i++)
						dummy2[sccId[i]] |= (board[s][i] - '0');
				}
				for (i = 0; i < sccCount; i++)
					dummy[i] += dummy2[i];
			}

			for (auto it = sccadj[u].begin(); it != sccadj[u].end(); it++) {
				v = *it;
				if (dummy[*it] == 1) ans.push_back(_d{ sccs[u][0], sccs[v][0] });
				ind[*it]--;
				if (!ind[*it])
					q.push(*it);
			}
		}

		for (vector<int>& scc1 : sccs) {
			sz = (int)scc1.size();
			if (sz == 1) continue;
			for (i = 0; i < sz - 1; i++)
				ans.push_back(_d{ scc1[i], scc1[i + 1] });
			ans.push_back(_d{ scc1[sz - 1], scc1[0] });
		}

		printf("%d\n", (int)ans.size());
		for (_d& a : ans)
			printf("%d %d\n", a.u + 1, a.v + 1);
		puts("");
	}
	return 0;
}