본문으로 바로가기

[백준 1717] 집합의 표현

category 알고리즘/백준 알고리즘 2018. 4. 24. 18:23
글에 개요

백준 알고리즘 1717번 "집합의 표현" 문제입니다.
앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.
유니온 파인드 (Union-Find)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!
이 후 이 문제를 통해 확장할 수 있는 알고리즘이 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 1717] 줄 세우기https://www.acmicpc.net/problem/1717

참고할 글
  1. http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)
핵심 내용
  1. 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
  2. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행해야 한다.
  3. Disjoint-set 자료구조를 구현하는 문제입니다.


해결 방법
  1. parent[] 배열을 초기화 해줍니다.
  2. find(), union(), isSameParent() 메소드를 만들어 줍니다.
  3. 여기서 isSameParent()는 임의의 이름으로 만든 함수명입니다. find(), union() 메소드의 작동 원리만 파악하셔도 충분히 푸실 수 있는 문제입니다.
해결한 코드



백준 참고 내용

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB91733012197830.586%

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제 입력 1 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 

NO
NO
YES



댓글을 달아 주세요