[백준/BOJ] 백준 3865번 : 학회원

www.acmicpc.net/problem/3865

3865번: 학회원

multimap<string, string> adj;를 통해 그래프를 만들고 깊이 우선 탐색(dfs)을 통해 문제를 해결했다.

 

코드

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

int n;
multimap<string, string> adj;
map<string, int> visited;

void Pre()
{
	adj.clear();
	visited.clear();
}

int Solve(string here)
{
	visited[here] = 1;

	//here가 그룹이 아닌 사람일때
	if (adj.count(here) == 0)
		return 1;

	int ret = 0;
	multimap<string, string>::iterator it = adj.lower_bound(here);
	for (int i = 0; i < adj.count(here); i++)
	{
		if (visited[(*it).second] == 0)
		{
			ret += Solve((*it).second);
		}
		it++;
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	while (1)
	{
		Pre();

		cin >> n;

		if (n == 0)
			break;

		string first_group = ""; //제일 처음 주어지는 학회
		bool first_group_check = false;
		for (int i = 0; i < n; i++)
		{
			string input;
			cin >> input;

			string group = "";
			bool group_check = false;
			string member = "";
			for (int j = 0; j < input.size(); j++)
			{
				if (group_check == false)
				{
					if (input[j] == ':')
					{
						group_check = true;

						visited.insert(make_pair(group, 0));

						if (first_group_check == false)
						{
							first_group = group;
							first_group_check = true;
						}
					}
					else
						group += input[j];
				}

				else
				{
					if (input[j] == ',' || input[j] == '.')
					{
						adj.insert(make_pair(group, member));
						visited.insert(make_pair(member, 0));
						member = "";
					}

					else
						member += input[j];
				}
			}
		}

		cout << Solve(first_group) << "\n";
	}


	return 0;
}