문제 출처
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 10 - 실전문제 2. 팀 결성
제한
- 시간 제한 : 2 초
- 메모리 제한 : 128 MB
문제
- 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1개의 팀이 존재한다. 이때 선생님은 ‘팀 합치기’ 연산과 ‘같은 팀 여부 확인’ 연산을 사용할 수 있다.
- ‘팀 합치기’ 연산은 두 팀을 합치는 연산이다.
- ‘같은 팀 여부 확인’ 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
- 선생님이 M개의 연산을 수행할 수 있을 때, ‘같은 팀 여부 확인’ 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다.(1 <= N, M <= 100,000)
- 다음 M개의 줄에는 각각의 연산이 주어진다.
- ‘팀 합치기’연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
- ‘같은 팀 여부 확인’연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산이다.
- a와 b는 N 이하의 양의 정수이다.
출력
- ‘같은 팀 여부 확인’연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.
👀 풀이
- 유니온 파인드 연습문제다.
- 팀 합치기 함수와 루트 노드를 찾는 함수를 작성한 다음에 연산에 따라 호출했다.
- ‘같은 팀 여부 확인’연산 수행 시 부모가 같은지 확인한 후 결과를 출력하면 된다.
코드
