15723번: n단 논법

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

• 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <deque>
#include <bitset>

using namespace std;

vector <int> graph[27];


int bfs(int start,int find)
{
	bool visited[27] = { false, };
	queue<char> q;
	q.push(start);
	visited[start] = true;

	int ans = 0;

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		// 큐에서 하나의 원소를 뽑아 출력
		int x = q.front();
		if (find == x) {
			ans = 1;
		}
	
		q.pop();
		// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
	
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
				
			}
		}
	}
	return ans;
}
int main()
{
	int n;
	cin >> n;
	cin.ignore();
	for (int i = 0; i < n; i++) {
		string s1;
		getline(cin, s1);
		graph[s1[0] - 97].push_back(s1[5] - 97);
	}
	int m;
	cin >> m;
	cin.ignore();
	for (int i = 0; i < m; i++) {
		string s2;
		getline(cin, s2);
		int check=bfs(s2[0] - 97, s2[5]-97);
		if (check == 0) {
			cout << "F" << endl;
		}
		else cout << "T" << endl;
	}
}

• 알고리즘 분류: 너비우선 탐색
• 문제 해설

노드를 연결해주고 너비우선탐색을 이용하여 해당 명제가 참인지 알기 위해 "a이면 b이다"에서 a를 start노드로 탐색해나가면 되었다. 탐색하면서 b가 있으면 T를 출력, 찾지 못하면 F를 출력한다.