집합의 표현

문제

풀이

이 문제는 유니온 파인드 알고리즘을 사용하여 풀 수 있다.

유니온 파인드란 무엇일까?
1. 먼저 1~6까지 있을 때 세팅을 먼저 하자
표에서 첫째 줄은 노드 번호
둘째 줄은 부모 노드 번호 이다.

현재 노드와 부모 노드는 같다고 세팅을 하자

2. 1 -> 6 연결
   6의 부모 노드는 1로 변경 된 것을 볼 수 있다.
   그 이유는 부모 노드 1, 6 중 작은 값 1로 세팅을 하자
   

3. 1 -> 2 연결
   마찬가지로 2의 부모 노드는 1로 변경 된 것을 볼 수 있다.
   1, 2 중 1이 더 작기 때문에 작은 값으로 세팅하자
   

4. 5 -> 4 연결, 4 -> 3 연결
   

5. 2 -> 5 연결

2의 부모노드를 생각해보자
2 -> 1, 1 -> 1 의 경로로 1이 될 것이다.

6의 부모노드를 생각해보자
5 -> 4, 4 -> 3, 3 -> 3의 경로로 3이 될 것이다.
즉 1 > 3이므로

3의 노드값을 1로 변경해준다.

이제 6과 5이 연결되어 있는지 확인해보자
6의 부모노드는 6 -> 1, 1 -> 1 즉 1이 된다.
5의 부모노드는 5 -> 4, 4 -> 3, 3 -> 1 즉 1이 된다.
부모노드가 서로 같으므로 같은 집합, 같은 그래프에 속한다고 생각할 수 있다.

코드

for test_case in range(1):
    n, m = map(int, sys.stdin.readline().split())
    arr = [i for i in range(n + 1)]

    def getParent(node):
        if arr[node] != node:
            arr[node] = getParent(arr[node])
        return arr[node]

    def unionParent(a, b):
        a = getParent(a)
        b = getParent(b)

        if a > b:
            arr[a] = arr[b]
        else:
            arr[b] = arr[a]

    for _ in range(m):
        cmd, a, b = map(int, sys.stdin.readline().split())

        if cmd == 0:
            unionParent(a, b)

        else:
            if getParent(a) == getParent(b):
                print('YES')
            else:
                print('NO')
        print(arr)

getParent함수는 부모 노드를 찾는 함수이다.
arr[node] = getParent(arr[node])를 해주어야지 시간 초과가 발생하지 않는다.
해당 경로에 있는 노드를 부모 노드로 변경해주는 의미이다.

unionParent함수는 부모노드를 합치는 함수이다.
a, b의 부모 노드를 비교한다.
그래서 작은 값을 기준으로 합치는 함수이다.

그래서 같은 그래프에 있는 조건은 부모노드가 같을 때이다.
if getParent(a) == getParent(b): 조건으로 같을 때 비교한다.