[C++] 백준 3865번: 학회원

문제 링크

3865번: 학회원

문제 요약

학회에 속한 사람들이 주어진다. 학회에는 다른 학회가 속해 있을 수도 있다. 이때, 첫번째 학회에 속한 학회원의 수를 구해야 한다.

접근 방법

학회와 학회원을 정점으로 봤을 때, 한 학회에 속한 학회와 학회원은 간선으로 연결되었다고 볼 수 있습니다.

입력된 문자열을 파싱한 뒤에, 학회 또는 학회원에 대해 맵을 이용해서 번호를 붙입니다. 그리고, 각 학회에 대해, 학회에 속한 학회원이나 학회로의 간선을 정의합니다. 즉, 유향 그래프를 만들면 됩니다.

마지막으로, 첫번째 학회를 의미하는 정점에서부터 그래프를 탐색하면서, 진출 간선이 0인 정점의 수를 세서 출력하면 됩니다. 진출 간선이 0인 정점은, 학회가 아닌 학회원이라는 뜻이기 때문입니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1001;
vector<int> adj[MAX];
bool visited[MAX];

void init(void) {
	for (int i = 0; i < MAX; i++) adj[i].clear();
	memset(visited, false, sizeof(visited));
}

int dfs(int now) {
	visited[now] = true;

	int cnt = 0;
	for (auto& next : adj[now])
		if (!visited[next])
			cnt += dfs(next);

	return (adj[now].empty() ? 1 : cnt);
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	while (1) {
		int n;
		cin >> n;

		if (!n) break;

		init();

		int idx = 0;
		unordered_map<string, int> m;
		for (int i = 0; i < n; i++) {
			string str;
			cin >> str;

			string tmp = "";
			int from;
			for (auto& i : str) {
				if (isalpha(i))
					tmp.push_back(i);
				else if (i == ':') {
					if (m.find(tmp) == m.end())
						m[tmp] = idx++;
					
					from = m[tmp];
					tmp = "";
				}
				else if (i == ',' || i == '.') {
					if (m.find(tmp) == m.end())
						m[tmp] = idx++;

					adj[from].push_back(m[tmp]);
					tmp = "";
				}
			}			
		}

		cout << dfs(0) << '\n';
	}

	return 0;
}