이 문제는 Union & Find 문제이다.
공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진
원소들에 대한 정보를 저장하고 조작하는 자료구조
초기화에는 자신이 부모인 것으로 초기화 해준다.
그리고 나서 부모 - 자식 관계
즉, 문제에서 동맹관계를 알려주면
해당 부모 자식관계를 par[] 배열에 맺어준다
그런데 어차피
동맹의 동맹은 동맹이므로
최종적으로 가장 높은 root를 같은걸 가리키고 있으면
같은 동맹이란 사실을 알 수 있다.
그래서 find 펑션에서
가장 높은 root를 찾을 수있도록 재귀로 구현해주었다.
동맹관계를 맺어주는
type =0 이면
각각 부모 - 자식관계를 맺어주고
type =1 이면 가장 높은 root를 구해주는
find 펑션을 통해
그 값이 같은지 비교해서
출력해준다.
'DEVELOP > ALGORITHM' 카테고리의 다른 글
단순 2진 암호코드 (0) | 2020.01.14 |
---|---|
View 조망권 문제 (0) | 2020.01.14 |
KOITP - BFS / DFS 문제 풀기 (0) | 2018.06.11 |
KOITP 가장 많은수 ( count sort) (0) | 2018.06.08 |
백준 9663번 Nqueen 문제 풀이 (2) | 2018.06.08 |