취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17839번 문제인 Baba is Rabbit이다.
문제는 아래 링크를 확인하자.

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

X is Y꼴의 문장이 입력으로 들어온다.

각 문자열 S와 양의 정수를 일대일로 매칭시키고, 평소와 같이 정수를 인덱스로 갖는 그래프 위에서 문제를 해결한 뒤 정수들을 다시 매칭된 문자열로 돌려놓으면 문제를 편하게 풀 수 있다.

정수가 있을 때 문자열을 얻는 것은 string형 배열을 이용하여 간단하게 나타낼 수 있다.

반대로 문자열을 입력했을 때 대응되는 정수를 얻는 것은 map을 이용하여 간편하게 구현할 수 있다.

이 문제에서 Baba가 될 수 있는 것 중 Baba는 세지 않음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int idx = 1;
map<string, int> sI;
string iS[200001];
vector<int> G[200001];
bool visited[200001];

vector<string> ans;
void bfs() {
	queue<int> que;
	que.push(sI["Baba"]);
	visited[sI["Baba"]] = 1;

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto node : G[cur]) {
			if (visited[node]) continue;
			visited[node] = 1;
			ans.emplace_back(iS[node]);
			que.push(node);
		}
	}
}

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

	int N; cin >> N;
	while (N--) {
		string s1, s2;
		cin >> s1 >> s2 >> s2;
		int x, y;
		if (sI.find(s1) == sI.end()) {
			x = idx;
			iS[idx] = s1;
			sI.insert(make_pair(s1, idx++));
		}
		else x = sI[s1];
		if (sI.find(s2) == sI.end()) {
			y = idx;
			iS[idx] = s2;
			sI.insert(make_pair(s2, idx++));
		}
		else y = sI[s2];
		G[x].emplace_back(y);
	}

	if (sI.find("Baba") == sI.end()) return 0;

	bfs();

	sort(ans.begin(), ans.end());
	for (auto s : ans) cout << s << '\n';
}