[알고리즘] 그래프 알고리즘

그래프(Graph)

• 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조
• 서로 다른 개체(혹은 객체)(Object)가 연결되어 있다는 문제는 그래프 알고리즘 떠올리기
• 그래프 구현 방법
  1. 인접 행렬(Adjacency Matrix) : 2차원 배열 사용
     • 메모리 공간이 많이 필요하지만 특정 노드 간 간선의 비용을 O(1) 시간으로 즉시 알 수 있음
  2. 인접 리스트 (Adjacency List) : 리스트 사용
     
     • 간선의 개수인 O(E) 만큼만 메모리 공간이 필요하지만 O(V) 시간 소요

1.  

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

 

서로소 집합(Disjoint Sets)

• 공통 원소가 없는 두 집합
• 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 서로소 집합 자료구조는 union과 find 2개의 연산으로 작할 수 있어 union-find 자료구조라고도 불림
  • union(합집합): 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • find(찾기): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 트리 자료구조를 이용하여 서로소 집합을 계산하는 알고리즘은 다음과 같은 방식으로 동작
  1. union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인
     1. A와 B의 루트 노드 A’와 B’를 찾음
     2. A’를 B’의 부모 노드로 설정 (B' → A')
  2. 모든 union 연산을 처리할 때까지 1번 과정 반복
• 서로소 집합은 무방향 그래프에서 사이클을 판별할 때 사용
• 부모 테이블에는 루트 노드 값이 들어가기 때문에 두 노드씩 비교하면서 루트 노드가 같다면 사이클이 발생한 것으로 간주
• 시간 복잡도:  O(V+M(1+log(2-M/V) V))   <노드의 개수가 V개이고 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때>

 

신장 트리(Spanning Tree)

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

 

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

• 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 것을 최소 비용 신장 트리 알고리즘이라고 하며, 크루스칼 알고리즘이 대표적
  
  1. 간선 데이터를 비용에 따라 오름차순 정렬
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
     1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
     2. 사이클이 발생하는 경우 최소 신장 트리에 불포함
  3. 모든 간선에 대하여 2번 과정 반복
• 모든 간선에 대해 정렬한 뒤 거리가 짧은 간선부터 집합에 포함시키기 때문에 그리디 알고리즘으로 분류됨
• 시간 복잡도: O(ElogE)   <E: 간선의 개수>   

 

위상 정렬(Topology Sort)

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
• 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
• 위상 정렬 알고리즘은 진입 차수를 기준으로 동작
  • 진입 차수:
• 위상 정렬 알고리즘
  1. 진입 차수가 0인 노드를 큐에 넣는다
  2. 큐가 빌까지 다음의 과정 반복
     1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
     2. 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다
• 시간 복잡도: O(V+E)

 

---

그래프 알고리즘 문제

팀 결성

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

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

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

'팀 합치기' 연산은 0 a b형태로 주어지며, '같은 팀 여부 확인' 연산은 1 a b 형태로 주어진다.

//특정 원소가 속한 집합 찾기
func find_parent(_ parent: [Int], _ x: Int) -> Int{
    var parent = parent
    if parent[x] != x{
        parent[x] = find_parent(parent, parent[x])
    }
    return parent[x]
}
//두 원소가 속한 집합 합치기
func union_parent(_ parent: [Int], _ a: Int, _ b: Int) -> [Int]{
    var new_a = find_parent(parent, a)
    var new_b = find_parent(parent, b)
    var new_parent = parent
    
    if new_a<new_b{
        new_parent[new_b] = new_a
    }else{
        new_parent[new_a] = new_b
    }
    return new_parent
}

var input_data = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input_data[0], m = input_data[1]

var parent: [Int] = Array(repeating: 0, count: n+1)
for i in 0...n{
    parent[i] = i
}

for i in 0..<m{
    input_data = readLine()!.split(separator: " ").map{Int(String($0))!}
    var oper = input_data[0], a = input_data[1], b = input_data[2]
    
    if oper == 0{
        parent = union_parent(parent, a, b)
    }
    else if oper == 1{
        find_parent(parent, a) == find_parent(parent, b) ? print("YES") : print("NO")
    }
}

---

도시 분할 계획

동물원에서 막 탈출한 원숭이 한 마리가 세상을 구경하고 있다.
어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데, 마침 마을 사람들은 도로 공사 문제로 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 길이다.
그리고 길마다 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.
마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 마을에는 집이 하나 이상 있어야 한다.

일단 분리된 두 마을 사이에 있는 길들은 필요에 따라 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 없애고 나머지 길의 유지비의 합으로 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. 크루스칼 알고리즘을 이용하여 최소 신장 트리를 찾은 후, 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거한다. 그러면 최소 신장 트리가 2개의 부분 그래프로 나누어지며, 최적의 해를 만족한다.

//특정 원소가 속한 집합을 찾기
func find_parent(_ parent: [Int], _ x: Int) -> Int{
    var parent = parent
    if parent[x] != x{
        parent[x] = find_parent(parent, parent[x])
    }
    return parent[x]
}
//두 원소가 속한 집합을 합치기
func union_parent(_ parent: [Int], _ a: Int, _ b: Int) -> [Int]{
    var new_a = find_parent(parent, a)
    var new_b = find_parent(parent, b)
    var new_parent = parent
    
    if new_a<new_b{
        new_parent[new_b] = new_a
    }else{
        new_parent[new_a] = new_b
    }
    return new_parent
}

var input_data = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input_data[0], m = input_data[1]

var parent: [Int] = Array(repeating: 0, count: n+1)
for i in 0...n{
    parent[i] = i
}
//모든 간선을 담을 배열
var edges = [[Int]]()
//최종 비용을 담을 변수, 최소 신장 트리에 포함되는 간선 중 비용이 가장 큰 간선
var re: Int = 0, last = 0

for i in 0..<m{
    input_data = readLine()!.split(separator: " ").map{Int(String($0))!}
    var a = input_data[0], b = input_data[1], cost = input_data[2]
    edges.append([cost,a,b])
}

//
edges = edges.sorted{ $0[0] < $1[0] }

for edge in edges {
    var cost = edge[0], a = edge[1], b = edge[2]
    
    if find_parent(parent, a) != find_parent(parent, b){
        parent = union_parent(parent, a, b)
        re += cost
        last = cost
    }
}

print(re-last)

---

커리큘럼

동빈이는 온라인으로 컴퓨터공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 들어야만 해단 강의를 들을 수 있다.
동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다.
동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.
입력은 강의의 수 N과, 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 주어지며, 각 줄은 -1로 끝난다.

//큐 구현
public struct Queue<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }

  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}
let n = Int(readLine()!)!
//모든 노드에 대한 진입차수 0으로 초기화
var indegree: [Int] = Array(repeating: 0, count: n+1)
//각 노드에 연결된 간선 정보를 담기위한 그래프
var graph: [[Int]] = Array(repeating: Array(repeating: 0, count: 0), count: n+1)
//각 강의 시간
var time: [Int] = Array(repeating: 0, count: n+1)

//방향 그래프의 보든 간선 정보 입력받기
for i in 1...n{
    var data = readLine()!.split(separator: " ").map{Int(String($0))!}
    time[i] = data[0]
    for x in 1..<data.count-1{
        indegree[i] += 1
        graph[data[x]].append(i)
    }
}

//위산 정렬 함수
func topology_sort(){
    var result = time
    var q = Queue<Int>()
    
    //처음 시작할 때 진입차수가 0인 노드를 큐에 삽입
    for i in 1...n{
        if indegree[i] == 0{
            q.enqueue(i)
        }
    }
    
    //큐가 빌 때까지 반복
    while !q.isEmpty{
        var now = q.dequeue()!
        
        //해단 원소와 연결된 노드들의 집입차수에서 1 빼기
        for i in graph[now]{
            result[i] = max(result[i], result[now]+time[i])
            indegree[i] -= 1
            if indegree[i] == 0{
                q.enqueue(i)
            }
        }
    }
    for i in 1...n{
        print(result[i])
    }
}
topology_sort()