[백준 C++] 11097 도시 계획

문제

경기도의 어떤 한 도시는 새 구역을 건설해서 도시를 확장하려고 한다. 그래서 이 도시에서는 우리의 친구 남서를 비롯한 여러 유명 건축가들을 불러 디자인을 시켰다. 남서는 도로망 디자인 담당이 되었는데, 귀찮았던 나머지 구역 내의 지역들을 잇는 모든 도로를 일방통행으로 만들어버렸다. (다행히도, 두 지역 A B간에 A에서 B로 가는 도로, B에서 A로 가는 도로를 놓아 서로 연결할 수 있다.)

남서는 자신의 도로망 계획을 지도해 그려본 결과, 일방통행 도로들 때문에 몇몇 지역들에서 특정 지역으로 갈 수 없다는 것을 깨달았다. 이 문제를 해결하기 위해서, 남서는 놀라운 접근법을 사용하기로 했다: 종이에 갈 수 있는 모든 경우의 수를 쓰는 것이다. 좀 더 자세히 말하자면, 각 지역 j에 대해서 j로부터 갈 수 있는 모든 지역에 대해 리스트를 작성하는 것이다. 우리는 이 리스트를 도로망의 '갈 수 있는 지역 리스트'라고 부른다. (만약 A에서 B로 가는 길이, B에서 C로 가는 길이 있다면 A의 리스트에는 B,C가, B의 리스트에는 C가 적힐 것이다.)

그러나, 남서는 문제를 해결하던 도중 하드 디스크가 망가져 자기가 만든 도로망 계획을 모두 잃어버렸다. 그에게 남은 것은 책상 위의 종이 한 장 - '갈 수 있는 지역 리스트' 하나 뿐이다.

우리는 불쌍한 남서를 도와 이 '갈 수 있는 리스트'를 통해서 원래 도로망 계획을 알아내려고 한다. 물론, 한 '갈 수 있는 리스트'에 대해서 여러 도로망 구조가 만들어질 수 있다. 우리는 이 중에서 각 지역을 잇는 도로의 개수가 가장 적은 도로망 계획을 구하고자 한다. 그러면 아마도 남서에게 큰 도움이 될 것이다.

주어진 '갈 수 있는 지역 리스트'에 대해서 가장 적은 도로로 이루어진 도로망 계획을 구하여라.

입력

첫 라인에는 전체 테스트 케이스의 개수 t 가 주어진다. 각 테스트 케이스는 빈 줄로 구분된다.

각 테스트 케이스의 첫 줄에는 지역의 개수를 나타내는 수 n (1 ≤ n ≤ 300)이 주어진다. 각 지역은 1부터 n까지 번호가 부여되어있다. 그 다음 n줄은 각각 길이 n의 문자열이 주어진다. 각 i번째 줄은 지역 i로부터 갈 수 있는 지역들에 대한 정보를 나타낸다. 정확하게 말하자면, j번째 문자가 0이라면 지역 i에서 j로 갈 수 없는 것이고, j번째 문자가 1이라면 지역 i에서 j로 가는 방법이 하나 이상 존재하는 것이다. (물론, 지역 i에서 i로는 항상 갈 수 있다.)

주어진 '갈 수 있는 지역 리스트'는 실제로 하나 이상의 도로망을 구성할 수 있다.

출력

각 테스트 케이스에 대해서, 가장 적은 도로로 이루어진 도로망 계획을 구한다. 첫 번째 줄에는 도로의 개수 m (물론, 이 m은 가능한 한 작아야 한다!)이 주어진다. 그리고 그 뒤로 이어지는 m개의 줄에는 두 개의 수 ai와 bi (1 ≤ ai, bi ≤ n)을 출력한다. 이는 지역 ai 에서 bi로 가는 도로를 의미한다.

도로는 어떤 순서로 출력해도 상관 없다. 만약 하나 이상의 해가 존재한다면 그 중 어떤 것을 출력해도 문제 없다.

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

풀이

이 문제는 기존의 DFS를 이용해 SSC를 구하는 방법외 주어진
단방향 연결 테이블만으로도 SCC를 구할 수 있다. 이를 통해서
1. 각 정점이 속한 SCC번호를 계산, SCC에속한 정점들 계산
2. 입력된 단방향 연결테이블과 각 정점이 속한 SCC번호를 비교하여 서로다른 SCC간의 연결을 새로운 2차원테이블에 저장
3. 2번에서 구한 2차원테이블에 플로이드를 돌려서
연결 될 수 있는 중복된 요소를 제거
4. 제거된 2차원테이블. 즉 SCC간의 연결을 결과에저장
5. SCC내부 요소간의 사이클을 만드는 연결을 결과에 저장
6. 결과 출력

이제 자세히 알아보자.

0. 필요한 요소들
   
   
   
1. 각 정점이 속하는 SCC번호, 또 SCC를 구성하는 정점들 계산
   
   기존의 DFS방법으로 SCC를 구해도 상관은 없습니다.
   
   
2. 두 정점 x, y가 x->y로 이동가능할때 두 정점이 서로 다른 SCC에 속하면 두 SCC가 서로 연결됨을 새로운 테이블에 저장합니다.
   
   
   
3. 2번에서 구한 2차원테이블은 중복된 연결이 있으므로 중복을 제거해야함
   주석으로 설명을 달아 놓긴했으나 결국 하나의 SCC:x에서 다른 SCC:y로 갈 수 있을때 중간에 어떤 SCC:k를 거쳐 갈 수 있으면
   문제에서는 최소 가짓수를 출력 하라 했으니 SCC:x -> SCC:y는 제거해야함.
   이때 플로이드알고리즘을 사용.
   
   
4. 위에서 중복을 제거한 SCC간 연결테이블을 결과로 저장
   
   문제에서 순서가 상관없다고 했으니 SCC의 첫번째요소끼리의 연결을 결과로 저장합니다.
   
   
5. 마지막으로 각 SCC마다의 내부 구성원간의 연결을 결과에 저장
   하나의 큰 사이클을 이루도록 결과를 저장합니다.

여기서 2번과 5번의 순서는 바뀌어도 논리에는 이상없습니다.

아래는 전체 코드입니다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
#define MAX 301
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int T, N, SCCcnt=1, resCnt;
//edge[x][y] : x -> y 로 이동가능 (단방향연결 되있음)
//SCCedge[x][y] x번SCC -> y번SCC 로 이동가능 (단방향연결 되있음)
bool edge[MAX][MAX], SCCedge[MAX][MAX]; 
int SCCNum[MAX];
vi SCC[MAX];
vii res;
void init();
void func();

void init() {
	sc("%d", &T);
}

//프로그램 메인 로직
void func() {
	while (T--) {
		sc("%d", &N);
		rrep(i, 1, N + 1) 
			rrep(j, 1, N + 1) 
				sc("%1d", &edge[i][j]);

		//모든 정점간의 단방향 연결정보가 주어지면
		//기존에 DFS방법말고도 SCC를 더 쉽게 만들 수 있음
		//아래의 1번과정으로도 충분히 SCC를 구할 수 있어요.

		//1. 각정점이 속하는 SCC를 구함
		//SCCNum[x] : 정점x가 속한 SCC번호
		//SCCNum[y] : 정점가 속한 SCC번호
		rrep(x, 1, N + 1) {
			if (SCCNum[x] == 0) { //정점x가 어느 SCC에도 속하지 않는다면
				SCCNum[x] = SCCcnt++; //정점x의 SCC번호를 새로이 지정
				SCC[SCCNum[x]].pb(x); //정점x를 새로운SCC의 초기 구성원으로 넣음
			}
			rrep(y, 1, N + 1) {
				//두 정점x, y가 서로에게 도달 가능하면 하나의 사이클이며 하나의 SCC이다.
				//정점y가 아직 어느 정점에 속하지 않았을때 정점y를 정점x가 속한 SCC그룹의 구성원으로 추가합니다.
				if (x != y && !SCCNum[y] && edge[x][y] && edge[y][x]) {
					SCCNum[y] = SCCNum[x]; //정점y의 SCC번호를 새로이 지정
					SCC[SCCNum[y]].pb(y);  //SCC번호에 정점y를 구성원으로 편입
				}
			}
		}

		//2. 서로 다른 SCC간 간선 연결
		rrep(x, 1, N + 1)
			rrep(y, 1, N + 1) {
				int numX = SCCNum[x]; //정점x가 속한 SCC번호
				int numY = SCCNum[y]; //정점y가 속한 SCC번호
				//정점x 에서 y로 갈수있고 두 정점이 서로다른 SCC에 속하면
				//정점x가속한 SCC에서 정점 y가 속한 SCC로 이동가능함을 저장
				if (edge[x][y] && numX != numY)
					SCCedge[numX][numY] = true;
			}

		//3. SCC간 연결된 간선중 중복을 제거
		//x번SCC -> y번SCC로가는 경로는
		//x번SCC -> k번SCC -> y번SCC 로 갈 수 있다면
		//최소 경로를 위해 제거해야하는것.
		//따라서 가능하면 SCCedge[numX][numY]를 불가능으로 바꾸어주어야함
		rrep(numK, 1, SCCcnt + 1) 
			rrep(numX, 1, SCCcnt + 1) 
				rrep(numY, 1, SCCcnt + 1)
					if (SCCedge[numX][numY] && SCCedge[numX][numK] && SCCedge[numK][numY])
						SCCedge[numX][numY] = false;


		//4. SCC간의 연결 저장
		//순서는 상관없으니 두SCC의 가장 첫번째 원소끼리 연결을 저장
		rrep(i, 1, SCCcnt) {
			rrep(j, 1, SCCcnt) {
				if (SCCedge[i][j]) {
					res.pb(mp(SCC[i][0], SCC[j][0])); //두 SCC를 구성하는 첫번째 정점을 끼리 연결을 저장
					resCnt++;
				}
			}
		}

		//5. 각SCC 내부 정점간 연결 저장
		rrep(k, 1, SCCcnt) {
			if (sz(SCC[k]) >= 2) {
				rrep(i, 1, sz(SCC[k])) {
					int x = SCC[k][i - 1]; //SCC의 구성원 정점x
					int y = SCC[k][i]; //SCC의 구성원 정점y
					res.pb(mp(x, y)); //두 정점 x, y가 연결됨(x -> y)을 저장
					resCnt++;
				}
				//SCC의 마지막정점과 SCC의 처음 정점을 연결해주어야 사이클이 완성
				res.pb(mp(SCC[k][sz(SCC[k]) - 1], SCC[k][0])); 
				resCnt++;
			}
		}


		//4. 결과 출력
		pr("%d\n", resCnt);
		rep(k, resCnt)
			pr("%d %d\n", res[k].first, res[k].second);

		//초기화
		resCnt = 0;
		SCCcnt = 1;
		res.cls();
		rrep(i, 1, N + 1) {
			SCC[i].cls();
			SCCNum[i] = 0;
			rrep(j, 1, N + 1) {
				edge[i][j] = false;
				SCCedge[i][j] = false;
			}
		}
	}
}

int main(void) {
	init();
	func();

	rt 0;
}

백준 플레4 달성!!!
학부졸업전에 달성하고자했던 목표가 플레4 였는데 생각보다 빨리 달성했다!
이제 하루종일 코딩만하지말고 다른 공부도 겸해야겠다..