[BOJ 26942 // C++] Gruppindelning

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

 

이번에 볼 문제는 백준 26942번 문제인 Gruppindelning이다.
문제는 아래 링크를 확인하자.

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

26942번: Gruppindelning

문제의 상황을 주어진 각 아이들을 노드로, 서로 같이 있고 싶어하는 관계를 에지로 하는 그래프로 모델링하자.

 

위의 그래프의 각각의 connected component에 대응되게끔 아이들을 그룹으로 나누는 것이 가장 많은 그룹을 만드는 방법임을 관찰해 문제를 해결해주자.

 

connected component의 개수를 세는 것은 DFS 등의 그래프 탐색 알고리즘 또는 disjoint set 등의 자료구조를 이용해 간단히 할 수 있다.

 

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

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

int N, M;
map<string, int> mp;
vector<int> G[101];
bool visited[101];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto& nxt : G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		mp.insert({ s,i });
	}
	cin >> M;
	while (M--) {
		string s1, s2; cin >> s1 >> s2;
		int x = mp[s1], y = mp[s2];
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) ans++, dfs(i);
	}

	cout << ans;
}