백준 2224번 : 명제 증명

문제 링크 : www.acmicpc.net/problem/2224

내 풀이(2021.1.26.) :

#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V 'z' - 'A' + 1 // 노드 개수의 최대값

int V, E; // V : 노드의 개수, E : 간선의 개수
vector<vector<int>> VV_info(MAX_V + 1, vector<int>(MAX_V + 1, INT_MAX)); // 모든 노드에서 모든 노드까지의 최단 거리

void floyd_warshall() { // 플로이드 워셜
	// 자기 자신에게 가는 간선값은 0
	for (int i = 1; i <= V; i++) {
		VV_info[i][i] = 0;
	}
	
	// 점화식 수행
	for (int k = 1; k <= V; k++) {
		for (int a = 1; a <= V; a++) {
			for (int b = 1; b <= V; b++) {
				if (VV_info[a][k] != INT_MAX && VV_info[k][b] != INT_MAX) {
					VV_info[a][b] = min(VV_info[a][b], VV_info[a][k] + VV_info[k][b]);
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	V = MAX_V;
	cin >> E;

	// 노드/간선 정보 초기화
	for (int i = 0; i < E; i++) {
		string a, x, b; cin >> a >> x >> b;
		VV_info[a[0] - 'A' + 1][b[0] - 'A' + 1] = 1;
	}

	floyd_warshall();

	int cnt = 0;
	for (int a = 1; a <= V; a++) {
		for (int b = 1; b <= V; b++) {
			if ((VV_info[a][b] != INT_MAX) && (VV_info[a][b] != 0)) cnt++;
		}
	}
	cout << cnt << endl;

	for (int a = 1; a <= V; a++) {
		for (int b = 1; b <= V; b++) {
			if ((VV_info[a][b] != INT_MAX) && (VV_info[a][b] != 0))
				cout << (char) (a + 'A' - 1) << " => " << (char) (b + 'A' - 1) << "\n";
		}
	}

	return 0;
}

아스키 코드 상에 대문자와 소문자가 연속으로 붙어있는 줄 알았는데, 알고 보니 떨어져 있었다.

따라서 MAX_V를 52로 하면 out of index error가 발생하므로 'z'-'A'+1로 해야 한다.

 

출처 : https://ko.wikipedia.org/wiki/ASCII