[유니온파인드] 1717번, 1976번

1. 집합의 표현

링크 - https://www.acmicpc.net/problem/1717

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**5)

#특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]= find_parent(parent,parent[x])
    return parent[x]
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
n,m = map(int,input().split())
parent = [0]*(n+1) #부모 테이블 생성

#부모테이블의 값을 자기 자신으로 초기화
for i in range(1,n+1):
    parent[i]=i

#union 연산을 각각 수행
for i in range(m):
    u, a,b = map(int,input().split())
    if u==0:
        union_parent(parent,a,b)
    else:
        if find_parent(parent,a)==find_parent(parent,b):
            print("YES")
        else:
            print("NO")

union_find 알고리즘을 이용하는 문제였다.
말귀를 못알아먹어서 처음에는 그냥 한 집합에 입력들 다 넣고 있는지 확인하면 되는거 아니야? 했는데,
1 7 1이 입력으로 들어오면
7과 1이 같은 집합에 속해있느냐를 물어보는 문제였다. 그래프로 이해하면 쉬울 듯 하다. (내가 그럼)

같은 집합에 속해있는지 확인하기 위해서는 부모노드가 같은지를 확인하면 되고, 둘의 부모노드가 같다면 Yes.... 아니라면 NOoooo.....를 출력하면 되는 문제였다.

재귀의 횟수 제약으로 setrecursionlimit()을 사용해야 했다.

2. 여행가자

링크 - https://www.acmicpc.net/problem/1976

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**5)

#특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]= find_parent(parent,parent[x])
    return parent[x]
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
n,m = map(int,input().split())
parent = [0]*(n+1) #부모 테이블 생성

#부모테이블의 값을 자기 자신으로 초기화
for i in range(1,n+1):
    parent[i]=i

#union 연산을 각각 수행
for i in range(m):
    u, a,b = map(int,input().split())
    if u==0:
        union_parent(parent,a,b)
    else:
        if find_parent(parent,a)==find_parent(parent,b):
            print("YES")
        else:
            print("NO")

런타임에러로 고생을 했다... 나는 recursionlimit때문인줄 알고 계속 제한 크기를 늘렸는데 다시보니까 인덱스에러였다.

백준에서 친절하게 인덱스 틀렸다고 알려줬는데 나혼자 뻘짓했다.

이것도 마지막에 여행경로를 입력받고, 여행 노드들의 부모노드를 확인해서 다른 부모노드를 출력하면 No, 다 같은 부모노드를 가진다면 Yes..를 출력하도록 했다.

+) 기타 그래프이론은 아직 dfs/bfs도 제대로 못풀기 때문에 나중에 하려다가 그냥 한 번 해봤다...
내일이나 나중에 유니온파인드 정리해야겠다..