[BOJ - 17839] Baba is Rabbit

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

17839번: Baba is Rabbit

 

문자열과 완전 탐색 알고리즘을 응용해보기 위한 문제인것 같다.

 

처음 입력을 받으면서 하나의 map을 생성해주었다.

 

그리고 다음으로 bfs로 완전 탐색하면서 Baba가 나올 수 있는 모든 경우의 수를 고려해줬다.

 

- 풀이 방법

1. 입력 받는다.

 

2. map을 만들어준다.

 

3. bfs 탐색

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

using namespace std;

int n;
map<string, vector<string>> dict;
map<string, int> visited;
queue<string> q;

int main(void) {

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		string p, is, q;
		cin >> p >> is >> q;
		
		dict[p].push_back(q);
	}

	string Baba = "Baba";

	vector<string> ans;

	q.push("Baba");

	while (!q.empty()) {
		string cur = q.front();
		q.pop();

		for (int i = 0; i < dict[cur].size(); i++) {
			if (visited[dict[cur][i]] != 0) continue;
			visited[dict[cur][i]] += 1;
			ans.push_back(dict[cur][i]);
			q.push(dict[cur][i]);
		}
	}

	sort(ans.begin(), ans.end());

	for (int i = 0; i < ans.size(); i++) {
		if(ans[i] != "")
			cout << ans[i] << "\n";
	}

	getchar();
	getchar();

	return 0;
}