# [이.취.코] Chap 10. 그래프 이론 - 팀 결성

- Author: @mildsalmon
- Published: 2021-09-04
- Updated: 2021-09-04
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-chap-10-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%ED%8C%80-%EA%B2%B0%EC%84%B1
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 그래프, 팀결성

---

# 1. 팀 결성

- 난이도
	- 중
- 풀이 시간
	- 20분
- 시간 제한
	- 2초
- 메모리 제한
	- 128MB
- 기출
	- 핵심 유형

### A. 문제

학생에게 0부터 N번까지 번호를 부여했다.    
모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다.    
팀 합치기 연산과 같은 팀 여부 확인 연산을 사용할 수 있다.    
  
- 팁 합치기  
    - 두 팀을 합치는 연산  
- 같은 팀 여부 확인  
    - 특정 두 학생이 같은 팀에 속하는지 확인

##### a. 입력 조건

- 첫째줄에 N, M  
	 - 1 <= N, M <= 100,000  
- 다음 M개 줄에 각각 연산이 주어진다.  
	 - 팀 합치기는 0 a b (a 학생 팀과 b 학생 팀을 합친다)  
	 - 같은 팀 여부 확인 1 a b (a학생과 b학생이 같은 팀이지 확인)  
		- a, b는 N 이하의 양의 정수

##### b. 출력 조건

같은 팀 여부 확인 연산에 대해 YES, NO를 한줄씩 출력

##### c. 테스트 케이스

- 입력 예시

	```

	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

	```

- 출력 예시

	```

	NO
	NO
	YES

	```
	
### B. 내 답안

```python

def find_team(team, x):  
    if team[x] != x:  
        team[x] = find_team(team, team[x])  
    return team[x]  
  
  
def union_team(team, a, b):  
    a = find_team(team, a)  
    b = find_team(team, b)  
  
    if a < b:  
        team[b] = a  
    else:  
        team[a] = b  
  
  
n, m = map(int, input().split())  
  
array = []  
team = [0] * (n + 1)  
  
for i in range(1, n + 1):  
    team[i] = i  
  
for i in range(m):  
    c, a, b = list(map(int, input().split()))  
    array.append([c, a, b])  
  
for i in range(m):  
    c, a, b = array[i]  
  
    if c == 0:  
        union_team(team, a, b)  
    elif c == 1:  
        if find_team(team, a) == find_team(team, b):  
            print("YES")  
        else:  
            print("NO")  
  
# 20분 4초 / Pass / Time out

```

##### a. 회고

> 풀이

- 팀 합치기와 같은 팀 여부 확인을 보자마자 서로소 집합 알고리즘이 떠올랐다.

> 반성

- 구현이 처음이라 시간이 좀 걸렸다.

### C. 문제 해설

서로소 집합 알고리즘 문제로 N과 M의 범위가 모두 최대 100,000이다. 따라서 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간 복잡도를 개선해야 한다.

##### a. 책 답안

[python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/10/7.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년