[백준 C++] 4305 성격 진단 테스트

문제

남규는 어떤 성격 진단 테스트를 받게 되었다. 이 테스트는 선택지가 5개인 여러 개의 질문으로 이루어져 있으며, 각 질문은 5개의 활동 중에서 무엇을 제일 선호하는지를 반드시 하나만 고르도록 되어 있다.

당신은 오후 여가 시간에 무엇을 하시겠습니까?

(a) League of Legends
(b) The Binding of Isaac
(c) 옆에서 코딩하는 재혁이 괴롭히기
(d) 내일 시험이 있지만 시험공부 하지 않기
(e) 잠자기
각 활동들은 커다란 셋에서 무작위로 뽑혀졌다. 즉, "잠자기"라는 선택지가 여러 개의 질문에 걸쳐 등장할 수 있다.

남규가 선택한 답안은 다른 모든 답안보다 더 선호한다는 의미를 갖게 되며, 만약 남규가 A, B, C, D, E 중에서 A를 선택했다면, A는 B, C, D, E 각각에 대해 더 선호도를 갖고 있다는 뜻이다. 만약 어떤 질문에서 X가 Y보다 선호도가 높다는 것이 드러났고, 다른 어떤 질문에서 Y보다 Z가 선호도가 높다는 것이 드러났다면, X의 선호도는 Z보다도 높다는 사실을 도출해낼 수 있다.

그러나 남규는 테스트를 대충 치뤄서 모순적인 답안이 발생하게 되었다. 모순적인 답안은 어떤 X, Y에 대해서, X가 Y보다 선호도가 높다는 결과와 Y가 X보다 선호도가 높다는 결과가 동시에 존재하는 것을 의미한다. 이런 모순적인 답안이 발생하면 작성자는 인성파탄자로 검사된다. 그래서 남규는 테스트 한 번 잘못 쳤다고 졸지에 인성파탄자가 되고 말았다.

여러 개의 테스트와 대답한 데이터가 주어졌을 때, 테스트에 등장한 모든 활동들을 분할(partition)하되, 각 그룹에서는 어떤 두 쌍을 골라도 두 활동 사이에 모순이 존재하도록 하시오.

입력

입력은 여러 개의 테스트 케이스로 주어지며, 입력의 끝에는 0이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 질문의 개수 N이 주어진다. 이어서 N개의 각 줄에는 5개의 서로 다른 활동 이름이 주어지고, 그 옆에 작성자가 선택한 활동 이름이 주어진다. 작성자는 반드시 해당 줄에 존재하는 활동을 선택했으며, 모든 활동 이름은 영문 대문자 1글자이다.

출력

각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알파벳순으로 가장 앞에 오는 원소 기준으로 그룹들도 알파벳순으로 출력되어야 한다. 반드시 질문에 존재했던 활동들만을 출력해야 한다.

각 테스트 케이스의 사이에는 빈 줄을 하나 출력한다.

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

풀이

각 줄의 입력이 총 6개 의정점으로 a, b, c, d, e, f 라면
{a, b, c, d, e} != f 인 정점 x들이모두
x -> f 로 간선이 연결됨을 의미합니다.

따라서 vector등으로 간선을 구현할 수 있겠으나
문제는 그러면 중복으로 들어갈수있다.
따라서 set컨테이너등을 사용해도되나
필자는 2차원 bool배열로 bool A[x][f] 로 구현했다. 당연 x -> f로 도달 가능을 구현한것이다.
그리고 SCC를 구한뒤 모든 SCC요소를 오름차순으로 정렬해서 출력하면된다.

#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 
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::to_string;
//_UG std::max; //_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; }


//DFS로 각 정점마다의 SCC를 구함
int DFS(int &x, int& id, int (&P)[27], bool (&A)[27][27]
	, int (& group)[27], si& S, vector<vi>& SCC) {
	P[x] = ++id;
	S.ph(x);

	int parent = P[x];
	rrep(y, 1, 27) {
		if (A[x][y] == false) ct;
		if (P[y] == 0)
			parent = std::min(parent, DFS(y, id, P, A, group, S, SCC));
		else if (group[y] == 0)
			parent = std::min(parent, P[y]);
	}

	if (parent == P[x]) {
		vi scc;
		while (x) {
			int y = S.TT();
			S.PP();
			group[y] = sz(SCC) + 1; //정점y가 속한 SCC번호를 기록(방문체크겸용)
			scc.pb(y);
			if (y == x) br;
		}
		sort(all(scc));

		SCC.pb(scc);
	}

	rt parent;
}

//프로그램 메인 로직
void func() {
	while (1) {
		int N;
		sc("%d", &N);
		if (!N) br; //0 : 종료

		bool actList[27] = { false }; //보기로 나온 모든 대문자 체크
		//DFS에서 사용할 요소들/////////////////////
		int id = 0, P[27] = { 0 };
		bool finished[27] = { false }; //방문체크 용도
		bool A[27][27] = { false }; //정점x와 인접한 정점들을 가지는 리스트
		int group[27] = { 0 }; //각 정점이 속한 SCC 번호를 기록
		si S; //DFS에서사용할 스택
		vector<vi> SCC; //찾은 SCC들
		////////////////////////////////////////////

		rep(_, N) { //N줄 입력받음
			int act[5], choose;
			char in;
			rep(i, 5) {
				sc("%c%c", &in, &in);
				act[i] = in - 'A' + 1;
				actList[act[i]] = true;
			}
			sc("%c%c", &in, &in);
			choose = in - 'A' + 1;

			rep(i, 5)
				if (act[i] != choose) 
					A[act[i]][choose] = true; //act[i] -> choose로 이동가능함을 표시
				
		}

		//전체 SCC를 구함
		rrep(k, 1, 27) if (P[k] == 0 && actList[k]) DFS(k, id, P, A, group, S, SCC);
		sort(all(SCC));
		rep(i, sz(SCC)) {
			vi scc = SCC[i];
			rep(j, sz(scc)){
				pr("%c ", scc[j] + 'A' - 1);
			}
			pr("\n");
		}
		pr("\n");
	}
}

int main(void) {
	func();

	rt 0;
}