백준 2224 명제 증명 c++ (플로이드 와샬)

문제 출처 : https://www.acmicpc.net/problem/2224

2224번: 명제 증명

문제

수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.

논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.

어떤 참인 명제가 주어졌을 때, 이 명제가 참이므로 이 명제 자체도 증명될 수 있다고 할 수 있다. 하지만 “P => P”와 같은 명제는 항상 참이 되는데, 이런 식으로 전건과 후건이 같은 경우는 출력하지 않기로 한다.

N개의 참인 명제들이 주어졌을 때, 증명될 수 있는 명제를 모두 구해내는 프로그램을 작성하시오. 명제를 증명하는 방법은 여러 가지가 있을 수 있지만, 위에서 언급한 방법만을 사용하기로 한다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 참인 명제들이 주어진다. 명제는 "P => Q"의 꼴로 주어지는데, “=>”는 앞뒤가 공백으로 구분되어 있다. P나 Q는 명제를 나타내는 문자인데, 알파벳 대소문자 한 글자를 사용한다. 같은 명제가 여러 번 주어질 수도 있다.

출력

첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으로 정렬한다. 알파벳은 대문자가 소문자에 우선한다. 즉, 정렬했을 때 A, B, …, Z, a, b, …, z 순서로 나와야 한다.

알고리즘 분류

• 그래프 이론
• 플로이드–와샬

풀이

n개의 간선이 주어질 때, n 개의 간선의 전건에서 이어질 수 있는 모든 후건에 대해 탐색해야 한다.

즉, 모든 정점에서 모든 정점에 갈 수 있는지 없는지 확인하면 된다. 고로 플로이드 와샬 알고리즘을 사용한다.

 

n의 크기가 10000이라서 3중 포문을 사용하는 플로이드 와샬 알고리즘을 사용하면 시간 초과가 나는 거 아니야?

라고 생각할 수 있는데, 여기서 n은 간선의 개수를 뜻하며, 실제 플로이드 와샬이 돌아야 할 구간은 각 포문마다 A~z의 개수만큼이다.

 

본인은 명제를 확인하기 위한 2차원 배열을 bool dp[58][58]로 선언했다.

z의 아스키 코드 값은 122이고, A의 아스키 코드 값은 65이기 때문에, A의 인덱스를 0, z의 인덱스를 57로 사용하였다.

실제 A~z의 개수는 52개이지만, Z 와 a 사이에 6개의 다른 문자가 끼어있기 때문에 위와 같이 배열을 잡았다.

 

주의할 점은 입력에서 같은 명제가 나올 수 있다는 점, 전건과 후건이 같을 수 있다는 점이다.

나머진 코드를 보면 단번에 이해할 수 있을 것이다.

 

코드

#include <iostream>
#include <string>

using namespace std;

int n;
//1<=n<=10000
bool dp[58][58];
int cnt = 0;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	
	cin >> n;
	cin.ignore();
	for (int i = 0; i < n; i++) {
		string input;
		getline(cin, input);
		//a=>a인 경우 skip
		if (input[0] == input[input.length() - 1]) continue;
		//중복입력인 경우 skip
		if (dp[input[0] - 'A'][input[input.length() - 1] - 'A']) continue;
		cnt++;
		dp[input[0] - 'A'][input[input.length() - 1] - 'A'] = true;
	}

	//
	for (int k = 0; k < 58; k++) {
		for (int i = 0; i < 58; i++) {
			for (int j = 0; j < 58; j++) {
				//이미 참이라고 밝혀진 경우 스킵
				if (dp[i][j] || i==j)continue;
				//i=>k 이고, k=>j 이면 i=>j
				dp[i][j] = dp[i][k] && dp[k][j];
				if (dp[i][j])
					cnt++;
			}
		}
	}

	cout << cnt << '\n';
	for (int i = 0; i < 58; i++) {
		for (int j = 0; j < 58; j++) {
			if (dp[i][j]) {
				cout << (char)(i + 'A') << " => " << (char)(j + 'A')<<'\n';
			}
		}
	}
	return 0;
}