그래프 이론 문제

서로소 집합

공통 원소가 없는 두집합, 집합 간의 관계를 파악하기 위해서 서로소 집합 알고리즘을 사용할수 있다.

서로소 알고리즘은 union - find 연산으로 구성 ,모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾는다.

신장 트리

신장 트리는 하나의 그래프가 있을때 모든 노드를 포함하는 부분 그래플르 의미한다.

크루스칼 알고리즘

가능한 최소 비용의 신장 트리를 찾아주는 알고리즘

시간 복잡도는 O(ElogE) 간선의 비용이 작은 순서대로 차례대로 최소 신장 트리를 만들어 가는 그리디 알고리즘의 일종

위상 정렬 알고리즘

방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법

EX 선수 과목을 고려한 학습 순서 설정 문제

여행 계획

N개의 여행지 각 여행지는 1~N번까지의 번호로 구분

여행지가 도로로 연결되면 양방향 이동 가능

입력

• 첫째 줄에 여행자의 수 N 과 여행 계획에 속한 도시의 수 N
• 자N*N 행렬을 통해 서로 연결되어있는지 여부
• 한우링의 여행 계획에 포함된 여행지 번호

출력

• 여행 계획 가능 YES 불가능 NO

서로소 집합으로 여행 계획에 해당하는 모든 노드가 같은 집합에 속하기만 하면 가능한 여행

모범답안

# 특정 원소가 속한 집합을 찾기 
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(n):
    data = list(map(int,input().split()))
    for j in range(n):
        if data[j]==1 :
            union_parent(parent,i+1,j+1)

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

result = True 
for i in range(m-1):
    if find_parent(parent,plan[i]) != find_parent (parent,plan[i+1]):
        result =False

if result :
    print('yes')
else:
    print('no')

탑승구

g개의 탑승구 1번부터 g번까지의 번호로 구분

하나에 영구적으로 도킹해야 하며 다른 비행기가 도킹하지 않은 탑승구에만 도킹할수 있다.

도킹할수 없는 비행기가 나오는 경우 운행 중지

최대 몇개까지 도킹 가능?

입력

• 1≤G ≤ 100,000
• 1≤P ≤ 100,000

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

# 탑승구의 개수 입력 
g= int(input())
#비행기 개수 입력 
p = int(input())

parent = [0] *(g+1)

#부모 테이블 상에서 부모를 자기 자신으로 초기화 
for i in range(1,g+1):
    parent[i] = i

result =0 
for _ in range(p):
    data = find_parent(parent,int(input()))
    if data == 0 :
        break
    union_parent(parent,data,data-1) 
    result +=1 
print(result)

어두운 길

한 마을은 N개의 집과 M 개의 도로로 구성 각 집은 0 번부터 N-1번까지의 번호로 구분

모든 도로에는 가로등이 구비 특정한 도로의 가로등을 하루동안 켜기 위한 비용은

해당 도로의 길이와 동일

마을에 있는 임의의 두집에 대하여 가로등이 켜진 도로만으로도 오갈수 있도록 만들고자 한다.

입력

• 집의수 1≤N≤200,000 도로의수 (N-1 ≤ M ≤200,000)
• X,Y,Z 비용

출력

• 가로등을 비활성해서 절약할수 있는 최대 금액

크루스칼 알고리즘

전체 가로등을 켜는 비용 - 최소 신장 트리를 구성하는 비용

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)

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수 
edges= []
result = 0

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

#모든 간선에 대한 정보를 입력 
for _ in range(m):
    x,y,z =map(int,input().split())
    #비용순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용으로 설정 
    edges.append((z,x,y))

#간선을 비용순으로 정렬
edges.sort()
total = 0 

for edge in edges :
    cost,a,b = edge
    total+=cost 

    if find_parent(parent,a) != find_parent (parent,b):
        union_parent(parent,a,b)
        result +=cost 

print(total-result)