[BOJ 4305] 성격 진단 테스트

백준 4305번 성격 진단 테스트

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

4305번: 성격 진단 테스트

---

문제

5지 선다 중에 1개를 선택하는 성격 진단 테스트 입니다.

 

A B C D E 중에 A를 선택하면,

A가 B, C, D, E 보다 더 선호하는 보기라는 것입니다.

 

이렇게 여러 문항을 테스트 하다가 모순이 생길 수 있습니다.

모순이 있는 집단을 찾는 문제입니다.

---

풀이

모순이 생긴다는 의미는

A 보다 B를 선호한다고 골랐는데, 다른 문항에서 B 보다 A를 선호한다고 고른 것입니다.

(A > B && B > A)

 

이러한 부등호를 방향이 있는 간선으로 표시하면

A -> B && B -> A 가 됩니다.

이는 A와 B가 사이클을 이루게 됩니다.

 

즉, 그래프에서 사이클을 찾는 문제가 됩니다.

---

출처 : https://csacademy.com/app/graph_editor/

예제를 그래프로 그리면 아래와 같습니다.

 

간선이 많아서 보기 힘들지만, 여기서 사이클은 하나 밖에 존재하지 않습니다.

 

I, J, K 는 하나의 사이클로 판단해 한 줄로 출력하면 됩니다.

이 외의 나머지는 자기 자신으로만 구성된 사이클 이므로 한 줄에 하나씩만 출력해주면 됩니다.

 

사이클을 찾는 문제는 SCC 알고리즘으로 풀 수 있습니다.

https://kdr06006.tistory.com/6

강한 연결 요소 (Strongly Connected Component)

---

코드

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

bool check[26];
vector<int> adj[26];

struct SCC {
	int dfsn[26], dfsNumber;
	int sccn[26], sccNumber;
	bool finish[26];
	stack<int> S;

	void init() {
		dfsNumber = sccNumber = 0;
		for (int i = 0; i < 26; ++i) {
			finish[i] = false;
			dfsn[i] = sccn[i] = 0;
		}
	}

	int dfs(int cur) {
		int ret = dfsn[cur] = ++dfsNumber;
		S.push(cur);

		for (auto n : adj[cur]) {
			if (!dfsn[n]) ret = min(ret, dfs(n));
			else if (!finish[n]) ret = min(ret, dfsn[n]);
		}

		if (ret == dfsn[cur]) {
			++sccNumber;

			while (!S.empty()) {
				int t = S.top(); S.pop();
				sccn[t] = sccNumber;
				finish[t] = true;
				if (t == cur) break;
			}
		}

		return ret;
	}

	void solve() {
		for (int i = 0; i < 26; ++i) {
			if (check[i] && !dfsn[i])
				dfs(i);
		}

		for (int i = 0; i < 26; ++i) {
			if (!sccn[i]) continue;

			printf("%c ", i + 'A');
			for (int j = i + 1; j < 26; ++j) {
				if (sccn[i] == sccn[j]) {
					printf("%c ", j + 'A');
					sccn[j] = 0;
				}
			}
			printf("\n");

			sccn[i] = 0;
		}
	}
}scc;

void init() {
	for (int i = 0; i < 26; ++i) {
		check[i] = false;
		adj[i].clear();
	}
	scc.init();
}

void put_edge(char c1, char c2) {
	adj[c1 - 'A'].push_back(c2 - 'A');
}

int main()
{
	//freopen("input.txt", "r", stdin);

	while (true) {
		int n;
		scanf("%d", &n);
		if (n == 0) break;
		init();

		char arr[6];
		while (n--) {
			for (int i = 0; i < 6; ++i) {
				scanf(" %c", &arr[i]);
				check[arr[i] - 'A'] = true;
			}

			for (int i = 0; i < 5; ++i) put_edge(arr[5], arr[i]);
		}

		scc.solve();
		printf("\n");
	}
}

---

감사합니다.