<PART 2>그래프이론 예제

<2> 팀 결성
학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.
1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오

입력 조건:
1. 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다.
2. '팀 합치기' 연산은 0 a b 형태로 주어진다.
3. '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다.
출력 조건
1. '같은 팀 여부 확인'연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력한다.

입력 예시)
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

출력 예시)
NO
NO
YES

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드가 아니라면, 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return 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] * (v+1) #부모테이블 초기화
 
#부모테이블을 자기 자신으로 초기화
for i in range(0,n+1):
    parent[i] = i
 
#각 연산을 확인
for i in range(m):
    oper, a, b = map(int,input().split())
    #합집합 연산일 경우
    if oper == 0:
        union_parent(parent, a,b)
    #find연산일 경우
    elif oper == 1:
        if find_parent(parent,a) == find_parent(parent,b):
            print('YES')
        else:
            print('NO')
    

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드가 아니라면, 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return 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
 
# 노드의 개수와 간선개수(연산 횟수)받기
v,e = map(int,input().split()) 
parent = [0] * (v+1) #부모테이블 초기화
 
#모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
 
#부모테이블을 자기 자신으로 초기화
for i in range(0,n+1):
    parent[i] = i
 
#모든 간선에 대한 정보를 입력받기
for i in range(e):
    a, b, cost = map(int,input().split())
    #비용 순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost,a,b))
 
#간선을 비용순으 정렬
edges.sort()
last = 0 #최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
 
#간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent, a, b)
        result += cost
        last = cost
 
#최소 신장트리 1개에서 2개를 만들기 위해 맨 마지막의 간선을 제거
print(result-last)
    

from collections import deque
import copy
 
#노드의 개수 입력 받기
v= int(input())
#모든 노드에 대한 진입 차수는 0으로 초기화
indegree = [0] * (v+1)
#각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v+1)]
#각 강의 시간을 0으로 초기화
time = [0] * (v+1)
 
#방향 그래프의 모든 간선 정보를 입력받기
for i in range(1,v+1):
    data = list(map(int,input().split()))
    time[i] = data[0] #첫 번째 수는 시간 정보를 담고 있음
    for x in data[1:-1]: #1부터 -1인덱스전까지 -> 원소가 2개라면 출력x
        indegree[i] += 1 #전입 차수를 1증가
        graph[x].append(i) #정점 x에서 i로 이동 가능
 
#위상 정렬 함수
def topology_sort():
    result = copy.deepcopy(time)
    q = deque() #큐 기능을 위한 deque 라이브러리 사용
 
    #처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
 
    #큐가 빌 때까지 반복
    while q:
        #큐에서 원소 꺼내기
        now = q.popleft()
        #해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            result[i] = max(result[i], result[now]+ time[i])
            indegree[i] -= 1
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
 
#위상 정렬을 수행한 결과 출력
    for i in range(1,v+1):
        print(result[i])
 
topology_sort()
 
 

풀이: 이 문제는 위상 정렬 알고리즘의 응용문제이다. 그러므로 노드와 진입차수와 큐가 필요하다. 
초기에 노드의 개수(연산횟수), 진입 차수를 적을 indegree, 빈 그래프생성, 비용인 time을 저장할 [0] 초기화 리스트를 만든다.
그 다음, time과 선수과목을 입력받는다. 이때 time은 비용의 의미이므로 각 인덱스마다 넣어준다.
그 다음에, data[1:-1]이라는 방법을 이용한다. 이때 원소가 2개라면 아무것도 출력이 되지 않는다.
선수 강의의 개수마다 전입 차수를 1씩 더해주고 선수 강의 그래프에 자신을 추가시킨다.
이렇게 되면 노드마다의 전입 차수와 선수강의가 필요한 과목들이 정리가 된다.

그 후에 위상 정렬 알고리즘을 사용한다. 비용을 새로운 변수에 저장하고 큐를 위해 deque 라이브러리 사용한다.
진입차수가 0인, 즉 선수강의가 없는 노드부터 큐에 삽입한다. 그리고 큐가 빌때까지 반복하며 넣은 원소를 popleft를 이용하여 반환한다.
이때 입력을 예시로 들다면
graph[1] = [2,3,4]
graph[3] = [4,5] 이다.
그리고 result값은 선수강의를 다 들은 시간이므로 최대시간이다. 그러므로 result[2]= max(result[2], result[1]+time[2])가 된다. 잘 생각해보면 당연하다. 2과목은 1과목을 들어야 하고, 자신이 전입차수가 0일 때 실행되므로 전입차수가 있는지 없는지 모른다. 그러므로 자기 자신의 값인 result 값과 선수강의를 듣는 시간 + 자기 자신의 비용값중에 맥스를 택해야 한다. 
이렇게 result를 갱신한 후에 출력하면 된다.

배운 점: 위상 정렬 알고리즘은 더 자주 봐야할 것 같다. 원리는 간단한데 코드로 구현할 때 조금 헷갈리는 부분이 많다.