백준 4195번 친구 네트워크

문제 링크입니다: https://www.acmicpc.net/problem/4195

 

Union Find(=Disjoint Set) 자료구조를 통해 풀 수 있는 문제였습니다.

기존의 문제들과 비교해서 까다로웠던 점은 원소가 인덱스로 주어지지 않고 사람 이름으로 주어진다는 점이였습니다.

따라서 map<string, int>를 통해 사람 이름에 인덱스를 부여하여 문제를 푸는 것이 핵심이였습니다.

 

알고리즘은 아래와 같습니다.

1. 두 사람 이름을 입력 받습니다.

i) 기존에 등장한 이름이라면 map에서 인덱스를 찾습니다.

ii) 새로 나온 이름이라면 새로운 인덱스를 부여하고 map에 저장합니다.

2. 두 사람의 루트를 탐색합니다.

i) 같은 집합 내에 있다면 해당 집합의 크기를 출력해줍니다.

ii) 다른 집합에 있다면 두 집합을 합쳐준 뒤 집합의 크기를 출력해줍니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~