Union-Find, 크루스칼 알고리즘, 프로그래머스 문제풀이

1. Union FInd 관련 정리

노드와 간선이 연결되어 그래프가 주어질 때, 각 노드의 부모노드를 찾아 반환해주는 알고리즘

즉, 연결된 노드끼리 같은 그래프에 포함되어 있는지 확인하는 알고리즘

# 부모 노드 탐색 테이블에 위치한 값을 반환
def getgraph(graph, x):
    if graph[x] == x:
        return x
    else:
        return getgraph(graph, graph[x])

# 연결된 두 노드 중 부모 노드를 입력하는 함수
def uniongraph(graph, a, b):
    a = getgraph(graph, a)
    b = getgraph(graph, b)
    print(graph, a, b)
    if a < b:
        graph[b] = a
    else:
        graph[a] = b
        
        
# 연결된 두 노드가 동일한 부모를 가리키는지 확인하는 함수
def findgraph(graph, a, b):
    a = getgraph(graph, a)
    b = getgraph(graph, b)
    if a == b:
        return True
    else:
        return False

# 연결된 노드 리스트(1부터 7 까지 6만을 제외하고 연결됨)
ls = [[1,7],[1,4],[1,2],[1,5],[2,4], [2,5], [3,5]]

graph = [i for i in range(0, len(ls)+1)]
for a,b in ls:
    uniongraph(graph,a,b)

"""
[0, 1, 2, 3, 4, 5, 6, 7] 1 7
[0, 1, 2, 3, 4, 5, 6, 1] 1 4
[0, 1, 2, 3, 1, 5, 6, 1] 1 2
[0, 1, 1, 3, 1, 5, 6, 1] 1 5
[0, 1, 1, 3, 1, 1, 6, 1] 1 1
[0, 1, 1, 3, 1, 1, 6, 1] 1 1
[0, 1, 1, 3, 1, 1, 6, 1] 3 1
[0, 1, 1, 1, 1, 1, 6, 1] # idx 6을 제외하고 모두 1을 가리키고 있는 상태
"""

 

2. 크루스칼 알고리즘 정리

그래프에서 노드간 간선에 특정 값이 주어질때, 최소한의 간선으로(노드갯수n - 1) 합이 최소값 or 최대값을 기준으로 간선을 연결하는 알고리즘

 

1. 노드의 간선의 값의 오름차순, 내림차순에 따라 정렬

2. 사이클이 발생하면 Skip하도록 구현 

Ex. [1,2] [2,3] [3,1] 이렇게 될 경우 

"""
... Union Find 코드 위와동일
"""
# [[노드1, 노드2, 간선의 value]]
ls = [[1,7,12],[1,4,28],[1,2,67],[1,5,17],[2,4,24], [2,5,62], [3,5,20], [3,6,37], [4,7,13], [5,6,45], [5,7,73]]
graph = [i for i in range(0, len(ls)+1)]

# 1. 오름차순, 내림차순 정렬
ls = sorted(ls, key = lambda key=x:x[2])

for a,b in ls:
	# 2. 사이클 발생하는지 확인(부모노드가 같을 경우 사이클이 발생함)
	if findgraph(graph, a, b) == False:
	    uniongraph(graph,a,b)

 

3. 문제풀이(01.15)

1) 섬 연결하기

출처: 프로그래머스

난이도: LV3

풀이시간: 1h 30m

성공유무: 실패

틀린이유: Union FInd, 크루스칼 알고리즘에 대한 학습 부족

https://school.programmers.co.kr/learn/courses/30/lessons/42861

 

2) 단속카메라

출처: 프로그래머스

난이도: LV3

풀이시간: 1h 19m

성공유무: 특정 반례를 참고해 성공

틀린이유 or 어려웠던 부분

[[-20, 15], [-18, -13], [-12, -5], [-5, -3]]) 상황을 고려하지 못함

=> n번째의 나간시점이 n+1번째의 나간시점이 더 클 경우 나간시점 범위 재조정해야함

Ex. 15 >= -13의 경우 나간시점 범위 -20에서 -13까지