[백준 15723] n단 논법 (C++)

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

문제

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.

지무근은 중앙대 컴퓨터공학부 학생이다.

그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

 

입력

---

첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.

둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 “모든 a는 b이다”라는 의미이다. 하지만 “모든 b는 a이다”의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

n + 2번째 줄에 정수 m(1 ≤ m ≤ 10)이 주어진다. 그 다음 m개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

 

출력

---

m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

 

문제 풀이

---

그래프 탐색 문제.

 

a -> b이고 b->c면 a->b->c이므로 a->c이다. a is b 형식에서 각 알파벳에 따른 b들을 모두 저장해놓고 a에서 시작하는 탐색을 진행하여 우리가 원하는 전제를 만들 수 있는지 확인한다. 깊이 우선이나 너비 우선 중 아무거나 사용하여 k는 m이다라는 전제를 입력받았을 때, k에서 m까지 도달 가능한지 확인해주면 된다.

테스트 케이스가 여러 개이므로 한 번 탐색 후 큐나 스택, 방문 했는지의 여부를 저장하는 배열 등을 초기화해주는 것이 필요하다.

 

아래는 깊이 우선 탐색으로 구현한 코드.

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

bool* isVisited;
vector<int>* v;
stack<int> dfsStack;

void reset()
{
	for (int i = 0; i < 26; i++)
	{
		isVisited[i] = false;
	}
	while (!dfsStack.empty())
	{
		dfsStack.pop();
	}
}

bool search(int start, int end)
{
	dfsStack.push(start);
	isVisited[start] = true;
	while (!dfsStack.empty())
	{
		int top = dfsStack.top();
		bool isAdjacent = false;
		if (top == end)
		{
			return true;
		}
		for (int i = 0; i < v[top].size() && isAdjacent==false; i++)
		{
			int next = v[top].at(i);
			if (isVisited[next] == false)
			{
				isAdjacent = true;
				isVisited[next] = true;
				dfsStack.push(next);
			}
		}
		if (isAdjacent == false)
		{
			dfsStack.pop();
		}
	}
	return false;
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	string str;
	cin >> N;
	v = new vector<int>[26];
	isVisited = new bool[26];
	reset();
	cin.ignore();
	for (int i = 0; i < N; i++)
	{
		getline(cin, str);
		int start = str.at(0) - 97;
		int end = str.at(str.length() - 1) - 97;
		v[start].push_back(end);
	}
	cin >> M;
	cin.ignore();
	for (int i = 0; i < M; i++)
	{
		getline(cin, str);
		int start = str.at(0) - 97;
		int end = str.at(str.length() - 1) - 97;
		if (search(start, end) == true)
		{
			cout << "T" << "\n";
		}
		else
		{
			cout << "F" << "\n";
		}
		reset();
	}
	return 0;
}