1976 - 여행 가자

MST (Minimum Spanning Tree, 최소신장트리)를 하려면 크루스칼 알고리즘이 필요합니다. 근데 크루스칼 알고리즘을 사용하기 위해선 Union Find라는 알고리즘이 또 필요합니다.

 

그렇다면 차근차근 Union Find부터 알아봅시다.

 

Union Find란 서로가 속한 집합이 같은 집합인지 파악하는 것입니다. 즉, 학교 내의 학생 2명이 같은 반인지를 확인하는 알고리즘이라 생각하면 됩니다.

 

Union Find를 구현하기 위해 배열과 Tree를 사용할 수 있지만, 본 글에서는 배열로 다루는 Union Find를 설명할 것입니다.

---

Union Find를 구하기 위해선 총 3개의 행위(메소드)가 필요합니다.

 

우선 배열을 초기화하는 init과 각자의 Root를 구하기 위한 find, 서로 같은 Root로 설정하기 위한 union 함수입니다.

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

위 문제는 이를 활용한다면 간단히 해결할 수 있는 문제입니다.

 

def find(u):
	if u == route[u]: # 부모 노드와 찾으려는 값이 같으면 그 값이 바로 Root 노드입니다.
    	return u
    else:
    	return find(route[u]) # 아닌 경우엔 재귀함수로 찾아냅니다.

def union(u, v):
	# 우선 서로의 Root를 확인해서 같은지 아닌지를 확인합니다.
    u = find(u)
    v = find(v)
    
    if u == v: # 같은 경우 함수를 종료합니다.
    	return
    else: # 아닌 경우 더 낮은 값을 Root로 설정해줍니다.
    	if u < v:
        	route[v] = u
        else:
        	route[u] = v

N = int(input())
M = int(input())

mat = []
for i in range(N):
	temp = list(map(int,input().split()))
    mat.append(temp)

plan = list(map(int,input().split()))

route = [i for i in range(N + 1)] # 이 부분이 초기화 부분입니다.

for i in range(len(N)):
	for j in range(i, len(N)):
    	if mat[i][j] == 1: # 1인 경우에 서로가 이어져 있습니다. 그렇기에 서로 union 함수를 거치면 됩니다.
        	union(i + 1, j + 1)
            
check = find(plan[0])

for i in range(1, len(plan)):
	if check != find(plan[i]):
    	print("NO")
        break
else:
	print("YES")

위의 코드에서 find, union 부분을 자세히 보시면 충분히 이해할 수 있다고 생각합니다.

---

이상 1976 - 여행 가자였습니다. ^_^