[백준] 2224 - 명제 증명

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

2224번: 명제 증명

 

처음에 위상 정렬을 사용할 때 쓰는 indegree 배열을 이용해서 진입 간선이 0인 정점에 대해서 dfs를 모두 돌려주는 방식으로 진행을 하였다. 하지만 정점의 범위가 차례대로 주어지지 않는 문제이기 때문에, 처리하기 까다로울 것 같아서 플로이드-워셜 알고리즘을 사용하였다.

 

n이 알파벳 대, 소문자 총 52개이기 때문에 시간 안에 해결할 수 있다.

다만 주의할 점은, p => p와 같이 항등 명제같은 경우에는 처리하지 않는다는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, map[52][52];

int parse(char a) {
	if (a >= 'a' && a <= 'z') return a - 'a' + 26;
	return a - 'A';
}

char parse(int a) {
	if (a < 26) return a + 'A';
	return a + 'a' - 26;
}

int main() {
	cin >> n;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		char a, b; string c;
		cin >> a >> c >> b;
		map[parse(a)][parse(b)] = 1;
	}
	
	for (int k = 0; k < 52; k++) {
		for (int i = 0; i < 52; i++) {
			for (int j = 0; j < 52; j++) {
				if (i == j) continue;
				if (map[i][k] && map[k][j]) {
					map[i][j] = 1;
				}
			}
		}
	}

	for (int i = 0; i < 52; i++) {
		for (int j = 0; j < 52; j++) {
			if (i == j) continue;
			if (map[i][j]) {
				cnt++;
			}
		}
	}

	cout << cnt << '\n';

	for (int i = 0; i < 52; i++) {
		for (int j = 0; j < 52; j++) {
			if (i == j) continue;
			if (map[i][j]) {
				cout << parse(i) << " => " << parse(j) << '\n';
			}
		}
	}
}