문제

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

풀이

a는 b이다. (역은 성립하지 않는다.)

위의 논리식을 '유향 그래프'에 대응시키는 아이디어만 떠올리면, dfs로 쉽게 풀 수 있는 문제였다.

유의할 점이 몇 가지 있었다.

• substr 함수에서 out_of_range 에러 주의
• getline 함수 이용하여 공백을 포함한 문자열 입력 받기
• cin으로 입력 받고 나서 버퍼 비우기 (그 다음에 있는 getline 함수가 버퍼에 남아 있는 개행 문자를 읽고 바로 종료되지 않도록!!)
• 결론에 대한 T/F 여부를 출력한 다음, 전역 데이터 초기화 하기

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll; 
typedef pair<int, int> pii;

const int MAX = 60; 
vector<int> graph[MAX]; // 유향 그래프 
bool visited[MAX];
int N, M; // 전제, 결론 개수
bool connected = false; 

pii extractNodeNumber(string str) {
	string start = str.substr(0, 1);
	string end = str.substr(5, 1);
	int s = start[0] - 'a';
	int e = end[0] - 'a';
	return {s, e};
}

void dfs(int start, int end) {
	if(start == end){
		connected = true;
		return;
	}
	
	visited[start] = true;
	for(int i = 0; i < graph[start].size(); i++){
		int next = graph[start][i];
		if(!visited[next]){
			dfs(next, end);
		}
	}
}

void solution() {
	cin >> N;
	cin.ignore(); // 입력 버퍼 비우기

	for(int i = 0; i < N; i++){
		string premise;
		getline(cin, premise);

		pii node = extractNodeNumber(premise);
		graph[node.first].push_back(node.second);
	}

	cin >> M;
	cin.ignore(); // 입력 버퍼 비우기

	for(int i = 0; i < M; i++){
		string conclusion; 
		getline(cin, conclusion);

		pii node = extractNodeNumber(conclusion);

		// start -> end 연결되어 있는지 확인
		dfs(node.first, node.second);
		
		if(connected){
			cout << "T\n";
		}else{
			cout << "F\n";
		}

		// 각 케이스마다 전역 데이터 초기화 필수 
		connected = false;
		memset(visited, 0, sizeof(visited));
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	solution(); 
	
	return 0;
}