전달 폐포(Transitive Closure)란, 주어진 관계에서 원소들 간의 모든 가능한 전달적 관계를 도출하는 것을 의미합니다. 일반적으로 이를 구현하기 위해 플로이드(Floyd) 알고리즘이 사용됩니다.
아래 두 문제를 통해 전달 폐포를 계산하는 방법을 살펴보겠습니다.
문제 1 (POJ3660)
문제 링크: POJ3660
문제 설명: n마리의 소가 경기 대회에 참가하며, m개의 승패 관계가 주어집니다. 예를 들어, a와 b의 관계가 주어지면 a는 항상 b를 이깁니다. 또한 b가 c를 이긴다면, a도 c를 이깁니다. 몇 마리의 소에 대해 정확한 순위를 알 수 있는지 계산하세요.
해결 방안: 플로이드 알고리즘을 사용하여 모든 가능한 승패 관계를 전달적으로 계산합니다. u가 v를 이길 수 있으면 배열 d[u][v]를 1로 설정하고, 최종적으로 각 소에 대해 승패 관계가 완전히 결정되는 경우를 카운트합니다.
다음은 코드입니다:
#include
using namespace std;
const int MAX = 105;
int n, m;
int rel[MAX][MAX];
int main() {
cin >> n >> m;
memset(rel, 0, sizeof(rel));
for(int i = 0; i < m; ++i){
int x, y;
cin >> x >> y;
rel[x][y] = 1;
}
// 플로이드 워셜
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(rel[i][k] && rel[k][j]){
rel[i][j] = 1;
}
}
}
}
int count = 0;
for(int i = 1; i <= n; ++i){
bool possible = true;
for(int j = 1; j <= n; ++j){
if(i == j) continue;
if(!rel[i][j] && !rel[j][i]){
possible = false;
break;
}
}
if(possible) count++;
}
cout << count;
return 0;
}
문제 2 (POJ1094)
문제 링크: POJ1094
문제 설명: 대문자 문자열과 m개의 크기 비교 관계가 주어집니다. 이 정보로부터 모순 여부를 확인하고, 가능한 경우 문자열의 정렬 결과를 출력합니다. 만약 모순이 있다면 어느 관계에서 발생했는지를 출력합니다.
해결 방안: 각 입력된 관계마다 플로이드 알고리즘을 실행하여 모순 여부를 체크하고, 위상 정렬(Topological Sort)을 통해 정렬 가능성을 판단합니다.
다음은 코드입니다:
#include
using namespace std;
const int MAX = 30;
int n, m;
bool adj[MAX][MAX];
vector<int> graph[MAX];
int indegree[MAX];
bool visited[MAX];
char relations[1005][5];
bool hasContradiction(){
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
adj[i][j] |= (adj[i][k] && adj[k][j]);
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j && adj[i][j] && adj[j][i]) return true;
}
}
return false;
}
void topologicalSort(){
queue<int> q;
vector<int> order;
for(int i = 1; i <= n; ++i){
if(indegree[i] == 0) q.push(i);
}
while(!q.empty()){
int u = q.front(); q.pop();
order.push_back(u);
for(auto &v : graph[u]){
if(--indegree[v] == 0) q.push(v);
}
}
if(order.size() != n) cout << "순서를 결정할 수 없습니다.\n";
else{
for(auto &node : order) cout << char(node + 'A' - 1);
cout << "\n";
}
}
int main(){
while(cin >> n >> m && (n || m)){
memset(adj, 0, sizeof(adj));
memset(indegree, 0, sizeof(indegree));
for(int i = 1; i <= m; ++i){
cin >> relations[i];
int u = relations[i][0] - 'A' + 1;
int v = relations[i][2] - 'A' + 1;
adj[u][v] = true;
indegree[v]++;
}
bool contradiction = false;
for(int i = 1; i <= m && !contradiction; ++i){
if(hasContradiction()){
cout << "모순 발견: " << i << "번째 관계\n";
contradiction = true;
}
else{
topologicalSort();
if(order.size() == n){
cout << "정렬 완료: ";
for(auto &node : order) cout << char(node + 'A' - 1);
cout << "\n";
break;
}
}
}
if(!contradiction && order.size() != n) cout << "순서를 결정할 수 없습니다.\n";
}
return 0;
}