🧚알고리즘🧚-그래프- 유니온 파인드

🧚유니온 파인드🧚

 

두 노드가 같은 그래프에 속하는지 판별하는 그래프 알고리즘

 

union 연산 : 각 노드가 속한 집합을 하나로 합치는 연산

1. 리스트를 자신의 인덱스값으로 초기화하기
2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 연산을 수행
(인덱스값과 밸류값이 같지 않을 시 대표 노드가 아니므로 대표노드를 찾을 때까지 수행하여 그 값을 밸류값에 넣기)

 

find 연산 : 특정 노드가 속한 집합의 대표 노드를 반환하는 연산

1. 대상 노드 리스트의 '인덱스값==밸류값' 인지 확인
2. 아닐 시 밸류값이 가진 값을 인덱스값으로 한 노드로 이동
3. '인덱스값==밸류값' 일 때까지 1,2를 반복(재귀함수)
4. 대표 노드를 발견하면 거쳐나온 모든 노드의 밸류값을 대표 노드값으로 변경!

시간 복잡도 감소의 효과

이렇게 변경됨

---

🥇골드 5

1717번: 집합의 표현

import sys 
sys.setrecursionlimit(100000)
N,M = map(int,sys.stdin.readline().split())

def find(v): #find 연산 : v의 대표 노드값 반환
    if Nlist[v] == v:
        return v
    else:# 중요!! 경로 압축 부분!!
        Nlist[v] = find(Nlist[v])
        return Nlist[v] #전부 대표 노드로 값 바꾸기

def union(a,b) : # union 연산 : a 노드와 b노드의 대표 노드 연결
    Nlist[find(a)] = find(b)

def check(a,b): # a,b노드가 같은 집합에 있는지 확인
    if find(a) == find(b):
        return True
    return False

Nlist = [i for i in range(N+1)]

for _ in range(M):
    x,y,z = map(int,sys.stdin.readline().split())
    if x == 0: #집합합치기
        union(y,z)
    else: # 확인하기
        if check(y,z):
            print("YES")
        else:
            print("NO")

---

🥇골드 4

1976번: 여행 가자

여행 경로에 있는 도시들의 대표 노드가 다 같은가?

import sys 
sys.setrecursionlimit(100000)
N = int(sys.stdin.readline()) #도시 수
M = int(sys.stdin.readline()) #데이터리스트
cityRoad = [[0]]
for i in range(N):
    clist = list(map(int, sys.stdin.readline().split()))
    clist.insert(0,0)
    cityRoad.append(clist)
goinglist =  list(map(int, sys.stdin.readline().split()))

def find(v):
    if Nlist[v] == v:
        return v
    else:
        Nlist[v] = find(Nlist[v])
        return Nlist[v] 

def union(a,b) : 
    Nlist[find(a)] = find(b)


Nlist = [i for i in range(N+1)]

for i in range(1,N+1):
    for j in range(1,N+1):
        if cityRoad[i][j] == 1:
            union(i,j)

result = True

for i in range(1,M):
    if find(Nlist[goinglist[i-1]]) != find(Nlist[goinglist[i]]):
        result = False
        break

if result:
    print("YES")
else:
    print("NO")

 

글 읽기 - 휴 어디가 잘못된 걸까요..

아하! 파인드함수에서 대표노드 찾으면 바로 끝나므로 유니온 한 번 한다고 연결된 모든 노드들이 정리되는 것이 아니구나! 잘못생각햇음

---

🥇골드 4

1043번: 거짓말

각각의 파티마다 union 해서 거짓말 아는 사람 판별

find연산으로 과장이야기 가능한사람 판별 

import sys

cnt_party = int(sys.stdin.readline().rstrip().split()[1])
witness_set = set(sys.stdin.readline().rstrip().split()[1:])

party_list = []
possible_list = []

for _ in range(cnt_party):
    party_list.append(set(sys.stdin.readline().rstrip().split()[1:]))
    possible_list.append(1)

for _ in range(cnt_party):
    for i, party in enumerate(party_list):
        if witness_set.intersection(party):
            possible_list[i] = 0
            witness_set = witness_set.union(party)

print(sum(possible_list))

set 자료구조에서 union 가능

이 방법도 잇음