[백준] #1717 집합의 표현

이정연·2023년 4월 11일
0

CodingTest

목록 보기
144/165
post-thumbnail

문제 링크

설계

main

if __name__ == '__main__':
    n,m = map(int,input().split())
    parent = [i for i in range(n+1)]
    for _ in range(m):
        cmd,a,b = map(int,input().split())

        if cmd:
            if find(a,parent) == find(b,parent):
                print('YES')
            else:
                print('NO')
        else:
            union(a,b,parent)
  1. 명령어 1이 들어오면 a의 루트 노드와 b의 루트 노드를 비교한다.
  2. 명령어 0이 들어오면 a와 b를 합친다.

유니온 파인드의 자세한 설명은 여기를 참조한다.

전체 코드

import sys
sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline

def union(a,b,parent):
    a = find(a,parent)
    b = find(b,parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def find(node, parent):
    if node != parent[node]:
        parent[node] = find(parent[node], parent)
    return parent[node]

if __name__ == '__main__':
    n,m = map(int,input().split())
    parent = [i for i in range(n+1)]
    for _ in range(m):
        cmd,a,b = map(int,input().split())

        if cmd:
            if find(a,parent) == find(b,parent):
                print('YES')
            else:
                print('NO')
        else:
            union(a,b,parent)

🚨 재귀 제한을 걸어놓지 않으면 에러가 난다!

profile
0x68656C6C6F21

0개의 댓글