Union-Find 1976번 여행가자

union-Find 의 동작과정

다음과 같이 노드가 1,2,3번끼리 연결이 되어있다고 가정을 해봅시다.

 

다음 사진은 2번과 3번이 연결되었다고 가정을 해보았습니다. 그럼 재귀적으로 순차적으로 탐색을 진행해서

3번 노드는 2번으로 교체를 해주고 다시 2번 노드를 찾아서 1번과 연결이 되어있다면 더 작은값으로 변환을 해주어야합니다.

따라서 재귀적으로 호출을 진행하여 1,2,3번 노드는 1번으로 초기화를 진행해주면  1번과 2번과 3번이 연결되어있다고

가정할수있습니다.

 

여행가자 문제풀이

## # 두 원소가 속한 집합을 합치기
## 부모는 속한집합중에 제일 작은값을 가져야함
def union(x,y):
    x=find_union(x)
    y=find_union(y)
    if x<y:
        parent[y]=x
    else:
        parent[x]=y


## # 루트노드가 아니라면, 루트 노드를 찾을때까지 재귀적으로 호출한다.
def find_union(n):
    
    if parent[n]!=n:
        return find_union(parent[n])
    return n
    

n=int(input()) ##노드
m=int(input()) ##간선

parent=[0]*(n+1) ## 부모노드 초기화 !

# 예 parent[1]=1,parent[2]=2,parent[3]=3
for i in range(1,n+1): ## 부모노드에 나와 같은값을 넘어줌
    parent[i]=i
    

graph=[]
for i in range(1, n + 1):
    # 그래프로 표현
    graph = list(map(int, input().split()))

    # 현재 도시와 연결되어 있는 도시를 확인
    
    for j in range(1, len(graph) + 1):
        if graph[j - 1] == 1:
            union(i, j) # 두개의 도시를 합칩합으로 표현
             
plan=list(map(int,input().split())) ## 여행계획

res=set([find_union(i) for i in plan]) ## 하나의 그래프만 있는지 확인 !

if len(res)==1:
    print("YES")
else:
    print("NO")

 

 

동빈나- Union-Find

참고자료:https://www.youtube.com/watch?v=AMByrd53PHM