BOJ 4195 친구 네트워크
간결하게 풀어봤다.
- 테스트케이스가 여러 개 주어지는 문제이다.
변수와 자료구조들 초기화가 중요하다. 재할당 및 초기화 코드는 먼저 박아놓고 시작하자.
- '친구 관계가 주어진다' 는 두 사람의 관계가 양방향이다라고 해석할 수 있다. 즉, 무향 그래프라고 생각할 수 있다. (따라서 SSC 풀이도 가능해 보임)
혹은 '관계가 주어진다' 를 집합으로 생각한다면 분리 집합을 떠올리는 것은 그리 어렵지 않다.
- 분리 집합 풀이까지 떠올렸다면, 일반적인 경우와 달리 노드가 정수가 아닌 문자열로 주어지므로 이 부분을 어떻게 처리할지만 생각하면된다.
입력으로 주어지는 이름 문자열들을 분리 집합에서 사용할 parent 배열의 인덱스로 사용하기 위해서는 문자열-숫자 간의 맵핑이 필요하다.
map을 사용한다면 간단하게 구현이 가능하다.
SQL의 auto-increment 처럼 정수형 변수 하나를 선언해두고 1씩 늘려가면서 아직 맵핑이 안되었다면 맵핑, 맵핑이 이미 되었다면 그 값을 사용하게 하면된다.
보통은 분리 집합 구현할 때, parent 배열에는 자신의 부모 노드 번호만을 저장한다.
하지만 여기서 한 단계 더 나아가 부모 노드의 번호를 넣되, 최상위 노드에는 음수로 집합의 노드 수를 저장할 수 있다.
int find(int x) {
if (parent[x] < 0) return x; // 최상위 노드만 음수로 집합의 크기를 갖고 있음.
return parent[x] = find(parent[x]);
}
int Union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[a] += parent[b]; // 한쪽에는 기존 최상위 노드의 값끼리 더해줘서 union된 집합 크기를 저장.
parent[b] = a; // 나머지 한 쪽 노드는 다른 노드 자식으로 편입
}
return -parent[a];
}
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
using namespace std;
map<string, int> keyGen;
vector<int> parent;
// Union-Find 알고리즘의 find 함수
int find(int x) {
if (parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
// Union-Find 알고리즘의 union 함수
int Union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[a] += parent[b];
parent[b] = a;
}
return -parent[a];
}
void solution() {
int T;
string tmp[2];
cin >> T;
while (T--) {
int F, key = 0;
parent.assign(200001, -1);
keyGen.clear();
cin >> F;
for (int i = 0; i < F; i++) {
for (int i = 0; i < 2; i++) {
cin >> tmp[i];
if (keyGen[tmp[i]] == 0) keyGen[tmp[i]] = ++key;
}
cout << Union(keyGen[tmp[0]], keyGen[tmp[1]]) << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solution();
}
출처 : 내 머리