8 . 그래프 이론

8 . 그래프 이론

2021. 9. 8. 16:00ㆍ문제풀기/알고리즘

1. 그래프 관련해서 이미 배운 내용 정리

- 그래프랑 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다.

- 그래프와 트리 비교

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

- 그래프의 구현 방법 : 노드의 개수가 V, 간선의 개수가 E인 그래프일 때

	인접 행렬	인접 리스트
방식	2차원 배열을 사용하는 방식	리스트를 사용하는 방식
메모리 공간	O(V^2)	O(E)
특정 노드에서 다른 노드로 이어진 간선의 비용을 알기 위한 시간 복잡도	O(1)	O(V)

2. 서로소 집합

- 서로소 집합 : 공통 원소가 없는 두 집합

- 서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

=> union과 find, 이 2개의 연산으로 조작할 수 있다.

=> 따라서 union-find 자료구조라고 불리기도 한다.

- union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

- find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

(1) 서로소 집합 자료구조

- 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다.

=> 서로소 집합 계산 알고리즘

union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
A와 B의 루트 노드 A', B'를 각각 찾는다.
A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다)
모든 union 연산을 처리할 때까지 1~3번 과정을 반복한다.

- 서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.

- 예시) 전체 집합 {1,2,3,4,5,6}에서 (1,4), (2,3), (2,4), (5,6)의 union이 있다.

초기 단계에는 가장 먼저 노드의 개수 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.

노드번호 1 2 3 4 5 6

부모 1 2 3 4 5 6
union 1,4

노드번호 1 2 3 4 5 6

부모 1 2 3 1 5 6
union 2,3

노드번호 1 2 3 4 5 6

부모 1 2 2 1 5 6
union 2,4

노드번호 1 2 3 4 5 6

부모 1 1 2 1 5 6
union 5,6

노드번호 1 2 3 4 5 6

부모 1 1 2 1 5 5

(2) 기본적인 서로소 집합 알고리즘 소스코드

import sys
input = sys.stdin.readline

def find_parent(parent,x):
    if parent[x] != x:
        return find_parent(parent,parent[x])
    return 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 = [i for i in range(v+1)]

for i in range(e):
    a,b = map(int,input().split())
    union_parent(parent,a,b)

print('각 원소가 속한 집합: ', end='')
for i in range(1,v+1):
    print(find_parent(parent,i), end =' ')

print()

print('부모 테이블: ',end='')
for i in range(1,v+1):
    print(parent[i],end=' ')

=> 최악의 경우 find 함수가 모든 노드를 다 확인해야해서 시간복잡도가 O(V)가 된다.

(3) 경로 압축 기법으로 개선된 서로소 집합 알고리즘 소스코드

import sys
input = sys.stdin.readline

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


v,e = map(int, input().split())
parent = [i for i in range(v+1)]

for i in range(e):
    a,b = map(int,input().split())
    union_parent(parent,a,b)

print('각 원소가 속한 집합: ', end='')
for i in range(1,v+1):
    print(find_parent(parent,i), end =' ')

print()

print('부모 테이블: ',end='')
for i in range(1,v+1):
    print(parent[i],end=' ')

=> 시간 복잡도 : $$O(V+M(1+log_{2-M/V}{V}))$$

(4) 서로소 집합을 활용한 사이클 판별

- 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다.
=>서로소 집합을 활용한 사이클 판별 알고리즘

각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
그래프에 포함되어 있는 모든 간선에 대하여 1~3번 과정을 반복한다.

import sys
input = sys.stdin.readline

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


v,e = map(int, input().split())
parent = [i for i in range(v+1)]

cycle = False

for i in range(e):
    a,b = map(int,input().split())

    if find_parent(parent,a) == find_parent(parent,b):
        cycle = True
        break
    else:
        union_parent(parent,a,b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

3. 신장 트리(Spanning Tree)

- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

=> 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 하다.

4. 크루스칼 알고리즘 (Kruskal Algorithm)

- 최소 신장 트리 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘

- 크루스칼 알고리즘 : 가장 대표적인 최소 신장 트리 알고리즘

=> 그리디 알고리즘으로 분류된다.

- 크루스칼 알고리즘

간선 데이터를 비용에 따라 오름차순으로 정렬한다.
간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
모든 간선에 대하여 2번의 과정을 반복한다.

import sys
input = sys.stdin.readline

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


v,e = map(int, input().split())
parent = [i for i in range(v+1)]

edges = []
result = 0

for _ in range(e):
    a,b,cost = map(int,input().split())
    edges.append((cost,a,b))

edges.sort()

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

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

5. 위상 정렬 (Topology Sort)

- 위상 정렬은 정렬 알고리즘의 일종이다.

- 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

=> 즉, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것

=> 모든 선후 관계를 지키는 전체 순서를 계산 할 수 있다.

- 진입차수(Indegree) : 특정한 노드로 '들어오는' 간선의 개수를 의미

- 위상 정렬 알고리즘

진입차수가 0인 노드를 큐에 넣는다.
큐가 빌 때까지 다음의 과정을 반복한다.
1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2. 새롭게 진입차수가 0이된 노드를 큐에 넣는다.

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.

=> 다만, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많다.

- 위상 정렬의 시간 복잡도 : O(V+E)

from collections import deque

v,e = map(int, input().split())

indegree = [0]*(v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
    a,b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()

    for i in range(1,v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)

        for i in graph[now]:
            indegree[i] -= 1

            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i,end=' ')

topology_sort()

6. 문제

(1) 팀 결성

- 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용할 수 있다.

'팀 합치기' 연산은 두 팀을 합치는 연산이다.
'같은 팀 여부 확인'연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.

선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결괄르 출력하는 프로그램을 작성하시오.

<입력 조건>

첫째줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 <= N,M <= 100,000)
다음 M개의 줄에는 각각의 연산이 주어진다.
'팀 합치기'연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미이다.
'같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다. 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는 지를 확인하는 연산이다.
a와 b는 N 이하의 양의 정수이다.

<출력 조건>

'같은 팀 여부 확인' 연산에 대하여 한 줄에 하나씩 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

* 서로소 집합 알고리즘을 사용하자

import sys
input = sys.stdin.readline


def find_parent(parent,a):
    
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])
    
    return parent[a]


def union(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().rstrip().split())

parent = [i for i in range(n+1)]

for _ in range(m):
    order, a,b = map(int,input().rstrip().split())
    
    if order == 0:
        union(parent,a,b)
    else:
        if parent[a] == parent[b]:
            print("YES")
        else:
            print("NO")

(2) 도시 분할 계획

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

1647번: 도시 분할 계획

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번

www.acmicpc.net

* 크루스칼 알고리즘을 사용하자

import sys
input = sys.stdin.readline


def find_parent(parent,a):
    
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])
    
    return parent[a]


def union(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().rstrip().split())

parent = [i for i in range(n+1)]

edges = []
result = 0
last = 0

for _ in range(m):
    a,b,c = map(int,input().rstrip().split())
    edges.append((c,a,b))

edges.sort()

for c,a,b in edges:
    if find_parent(parent,a) != find_parent(parent,b):
        union(parent,a,b)
        result += c
        last = c
    
print(result - last)

(3) 커리큘럼

- 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다.

동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N = 3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자.

1번 강의 : 30시간
2번 강의 : 20시간
3번 강의 : 40시간

이 경우 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지의 최소 시간은 20시간, 3번 강의를 수강하기까지의 최소시간은 70시간이다.

동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.

<입력 조건>

첫째 줄에 동빈이가 듣고자 하는 강의의 수 N(1 <= N <= 500)이 주어진다.
다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다. 이때 강의 시간은 100,000 이하의 자연수이다.
각 강의 번호는 1부터 N까지로 구성되며, 각 줄을 -1로 끝난다.

<출력 조건>

N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다.

입력 예시
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

출력 예시
10
20
14
18
17

* 위상정렬 알고리즘을 사용하자

import sys
from collections import deque
import copy
input = sys.stdin.readline


def find_parent(parent,a):
    
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])
    
    return parent[a]


def union(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)

    if a<b:
        parent[b] = a
    else:
        parent[a] = b


n = int(input().rstrip())

edges = [0] * (n+1)
edges[0] = 100000
graph = [[] for _ in range(n+1)]
costs = [0] * (n+1)

for i in range(1,n+1):
    inputs = list(map(int,input().rstrip().split()))
    costs[i] = inputs[0]
    edges[i] = len(inputs)-2
    for j in range(1,len(inputs)-1):
        graph[inputs[j]].append(i)

results = copy.deepcopy(costs)
start = edges.index(0)

q = deque()
for i in range(1,n+1):
    if edges[i] == 0:
        q.append(i)

while q:
    now = q.popleft()

    for i in graph[now]:
        edges[i] -= 1
        results[i] = max(results[i], results[now] + costs[i])

        if edges[i] == 0:
            q.append(i)


print(results)

(4) 여행 계획

- 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면, 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N=5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다.

1번 여행지 - 2번 여생지
1번 - 4번
1번 - 5번
2번 - 3번
2번 - 4번

만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3번이라고 해봅시다. 이 경우, 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있습니다.

여행지의 개수와 여행지 간의 연결 정보가 주어졌을 때, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하세요.

<입력 조건>

첫째 줄에 여행지의 수 N과 여행 계획에 속한 도시의 수 M이 주어집니다. (1 <= N,M ,= 500)
다음 N개의 줄에 걸쳐 N x N 행렬을 통해 임의의 두 여행지가 서로 연결되어 있는지의 여부가 주어집니다. 그 값이 1이라면 서로 연결되었다는 의미이며, 0이라면 서로 연결되어 있지 않다는 의미입니다.
마지막 줄에 한울이의 여행 계획에 포함된 여행지의 번호들이 주어지며 공백으로 구분합니다.

<출력 조건>

첫째 줄에 한울이의 여행 계획이 가능하다면 YES를, 불가능하다면 NO를 출력합니다.

입력 예시
5 4
0 1 0 1 1
1 0 1 1 0
0 1 0 0 0
1 1 0 0 0
1 0 0 0 0
2 3 4 3

출력 예시
YES

* 서로소 집합 알고리즘을 사용하자

import sys
input = sys.stdin.readline

def find_parent(parent,a):
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])

    return parent[a]


def union(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().rstrip().split())
graph = [[] for _ in range(n+1)]
parent = [i for i in range(n+1)]

for i in range(1,n+1):
    inputs = list(map(int,input().rstrip().split()))
    for j in range(0,n):
        if inputs[j] == 1:
            graph[i].append(j+1)

plans = list(map(int,input().rstrip().split()))

for a in range(1,n+1):
    for b in range(1,n+1):
        union(parent,a,b)

result = []

for i in plans:
    result.append(parent[i])

if len(set(result)) == 1:
    print("YES")
else:
    print("NO")

(5) 탑승구

- 공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.

공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1<=gi<=G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

<입력 조건>

첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어집니다.
둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어집니다.
다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi(1 <= gi <= G)가 주어집니다. 이는 i번째 비행기가 1번부터 gi번째 (1 <= Gi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

<출력 조건>

첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

입력 예시 1
4
3
4
1
1

출력 예시 1
2

입력 예시 2
4
6
2
2
3
3
4
4

출력 예시 2
3

* 서로소 집합 연산을 사용하자

import sys
input = sys.stdin.readline

def find_parent(parent,a):
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])

    return parent[a]


def union(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().rstrip())
p = int(input().rstrip())

parent = [i for i in range(g+1)]

result = 0

for _ in range(p):
    now = int(input().rstrip())
    a = find_parent(parent,now)

    if a == 0:
        break

    else:
        union(parent,a,a-1)
        result += 1

print(result)

(6) 어두운 길

- 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.

정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

<입력 조건>

첫째 줄에 집의 수 N(1 <= N <= 200,000)과 도로의 수 M (N-1 <= M <= 200,000)이 주어집니다.
다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X,Y,Z가 주어지며, 공백으로 구분합니다. (0 <= X,Y < N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이는 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 2^31보다 작습니다.

<출력 조건>

첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력합니다.

입력 예시
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

출력 예시
51

* 크루스칼 알고리즘을 사용

import sys
input = sys.stdin.readline

def find_parent(parent,a):
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])

    return parent[a]


def union(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().rstrip().split())

parent = [i for i in range(n+1)]

edges = []
total = 0

for _ in range(m):
    x,y,z = map(int, input().rstrip().split())
    edges.append((z,x,y))
    total += z

edges.sort()
result = 0

for z,x,y in edges:
    if find_parent(parent,x) != find_parent(parent,y):
        union(parent,x,y)
        result += z

print(total - result)

(7) 행성 터널

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

2887번: 행성 터널

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이

www.acmicpc.net

* 크루스칼 알고리즘 사용하기

import sys
input = sys.stdin.readline

def find_parent(parent,a):
    if parent[a] != a:
        parent[a] = find_parent(parent,parent[a])

    return parent[a]

def union(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)

    if a<b:
        parent[b] = a

    else:
        parent[a] = b

n = int(input().rstrip())

parent = [i for i in range(n)]

x = []
y = []
z = []

for i in range(n):
    xx,yy,zz = map(int,input().rstrip().split())
    x.append((xx,i))
    y.append((yy,i))
    z.append((zz,i))

x.sort()
y.sort()
z.sort()

graph = []

for i in range(n-1):
    graph.append((x[i+1][0]-x[i][0], x[i+1][1], x[i][1]))
    graph.append((y[i+1][0]-y[i][0], y[i+1][1], y[i][1]))
    graph.append((z[i+1][0]-z[i][0], z[i+1][1], z[i][1]))

graph.sort()

def kruskal():
    result = 0
    for r,a,b in graph:
        if find_parent(parent,a) != find_parent(parent,b):
            union(parent,a,b)
            result += r

    return result

print(kruskal())

(8) 최종 순위

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

3665번: 최종 순위

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에

www.acmicpc.net

import sys
from collections import deque
input = sys.stdin.readline

t = int(input().rstrip())

for _ in range(t):
    n = int(input().rstrip())
    routes = [0] * (n+1)
    graph = [[] for _ in range(n+1)]
    last_year = list(map(int,input().rstrip().split()))

    for i in range(n):
        graph[last_year[i]] = last_year[i+1:]
        routes[last_year[i]] = i

    m = int(input().rstrip())

    for _ in range(m):
        a,b = map(int,input().rstrip().split())
        if b in graph[a]:
            graph[a].pop(graph[a].index(b))
            routes[a] += 1
            routes[b] -= 1
            graph[b].append(a)
        else:
            graph[b].pop(graph[b].index(a))
            routes[b] += 1
            routes[a] -= 1
            graph[a].append(b)

    def topology_sort():
        result = []
        q = deque()

        for i in range(1,n+1):
            if routes[i] == 0:
                q.append(i)

        while q:
            now = q.popleft()
            result.append(now)

            for i in graph[now]:
                routes[i] -= 1
                if routes[i] == 0:
                    q.append(i)

            if len(q)>1:
                print("IMPOSSIBLE")
                return 0

        if len(result) != n:
            print("IMPOSSIBLE")
            return 0

        for i in result:
            print(i, end = ' ')
        print()
        return 0

    topology_sort()

'문제풀기 > 알고리즘' 카테고리의 다른 글

7. 최단 경로 (다익스트라, 플로이드 워셜 알고리즘) (0)	2021.09.07
6. 다이나믹 프로그래밍 (0)	2021.09.01
4. 정렬 (0)	2021.08.08
3. DFS/BFS (0)	2021.08.04
2. 구현 (0)	2021.07.28

CSprout

CSprout

태그

최근글

댓글

공지사항

아카이브

1. 그래프 관련해서 이미 배운 내용 정리

2. 서로소 집합

(1) 서로소 집합 자료구조

(2) 기본적인 서로소 집합 알고리즘 소스코드

(3) 경로 압축 기법으로 개선된 서로소 집합 알고리즘 소스코드

(4) 서로소 집합을 활용한 사이클 판별

3. 신장 트리(Spanning Tree)

4. 크루스칼 알고리즘 (Kruskal Algorithm)

5. 위상 정렬 (Topology Sort)

6. 문제

(1) 팀 결성

(2) 도시 분할 계획

(3) 커리큘럼

(4) 여행 계획

(5) 탑승구

(6) 어두운 길

(7) 행성 터널

(8) 최종 순위

'문제풀기 > 알고리즘' 카테고리의 다른 글

관련글

티스토리툴바

노드번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

노드번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

노드번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	6