[알고리즘] 백준 15723번: n단 논법 (C++)

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

15723번: n단 논법

이번 문제의 포인트는 플로이드 와샬과 문자열을 변환시키는 일이었다.

n단 논법에 따라 a가 b라고 해서 b는 a가 되는 것은 아님을 알고 단방향 그래프로 표현해준다.

문자열은 getline을 썼고, n이나 m을 입력받고서는 버퍼에 '\n'가 남아있기 때문에 cin.ignore()을 해준다.

#include <iostream>
#include <string>
#define MAX (26 + 1)
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int n, m;

void floydWarshall() {
	for (int k = 1; k < MAX; k++) {
		for (int i = 1; i < MAX; i++) {
			for (int j = 1; j < MAX; j++) {
				if (i == j) continue;
				if (graph[i][k] == INF || graph[k][j] == INF) continue;
				if (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= 26; i++) {
		for (int j = 1; j <= 26; j++) {
			if (i == j) continue;
			graph[i][j] = INF;
		}
	}
	cin.ignore();
	for (int i = 0; i < n; i++) {
		string value;
		getline(cin, value, '\n');
		int s = value.front() - 96;
		int e = value.back() - 96;
		//cout << s << ' ' << e << '\n';
		graph[s][e] = 1;
	}
	floydWarshall();
	cin >> m;
	cin.ignore();
	for (int i = 0; i < m; i++) {
		string value;
		getline(cin, value, '\n');
		int s = value.front() - 96;
		int e = value.back() - 96;
		if (graph[s][e] == INF) cout << 'F' << '\n';
		else cout << 'T' << '\n';
	}
	return 0;
}