[알고리즘] 알고리즘 뽀개기 (5) : 그래프

알고리즘 뽀개기 Step 5 : 그래프

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.
해당 내용은 백준 알고리즘 강의를 참고하여 작성되었습니다.

그래프

자료구조의 일종으로, 정점(Node/Vertex)과 간선(Edge)으로 구성되어있으며, G = (V,E) 로 표현한다.

아래와 같은 개념을 추가로 알아두자.

• 경로 : 정점 2에서 1로 가는 경로
  • 2 -> 3 -> 1
  • 2 -> 1
• 사이클 : 정점 A에서 다시 A로 돌아오는 경로
• 단순 경로/사이클 : 같은 정점을 두 번 이상 방문하지 않는 경로/사이클로, 문제 등에서 특별한 언급이 없을 경우 일반적인 경로/사이클은 이를 의미한다. (보통 다시 방문하지 않음)
• 방향이 있는 그래프 : 위의 그래프와 같이 2 -> 1 처럼 간선에 방향이 있다. 2 -> 1 은 가능하지만 1 -> 2 는 불가하다.
• 방향이 없는 그래프 : 간선에 방향이 따로 없어, A-C는 A -> C, C -> A 가 둘다 가능한 것을 말하며, 양방향 그래프라고도 한다.
  표시가 주로 화살표가 아닌 직선으로 표시된다.
• 간선 여러개 : 두 정점 사이의 간선이 여러개가 존재할 수 있다. A - B를 연결하는 간선이 2개가 존재할 수 있으며, 이는 서로 다른 간선이다.
• 루프 : 간선의 양 끝점이 같은 경우로, A -> A 이다.
  
  
• 간선의 가중치 : 간선에 가중치가 있는 경우로, 주로 A->B로 이동하는 거리, 이동하는데 필요한 시간, 비용 등으로 언급된다.
  • 가중치가 따로 없는 경우는 다 동일하게 1이라고 생각하면 된다.
• 차수 : 각 정점들과 연결되어있는 간선들의 개수
  
  

그래프의 표현

기본적인 표현

주로 아래와 같은 방식으로 입력이 주어진다.

위 그래프는 정점이 6개, 간선이 8개로, G = (6,8) 이며, 간선에 방향이 없으므로, 방향이 없는 그래프이다.

• 정점 : {1,2,3,4,5,6}
• 간선 : {(1,2), (1,5), (2,5), (2,3), (3,4), (2,4), (4,5), (4,6)}

인접 행렬

정점의 개수를 V라고 할 때, VxV 크기의 이차원 배열을 이용한다.
A[i][j] = 1 (i -> j 로의 간선이 있을 때), 0 (없을 때)
를 이용해 아래처럼 표현할 수 있다.
(만일 가중치가 있을 경우, 1 이 아닌 가중치로 해당 값을 표현한다.)

양방향일 경우, A[i][j] = A[j][i] 가 된다.

인접 리스트

링크드 리스트를 이용해 구현한다.
A[i] = i 와 연결된 정점들을을 링크드 리스트로 포함한다.

링크드 리스트는 구현하는데 상대적으로 오래걸리고, 얼만큼 정점의 값들이 존재할지 모르기 때문에, 벡터 등 길이를 변경 가능한 배열을 이용해 구현한다.

만일 가중치가 있을 경우, 뒤에 오는 값으로 표현한다. (정점 , 가중치)

각 공간 복잡도는 인접행렬의 경우 O(V^2) 이고, 인접 리스트는 O(E) 이다.

간선 리스트

배열을 이용해 구현하며, 간선을 모두 저장하고 있다.

그래프의 탐색

• DFS : Depth First Search 로, 깊이 우선 탐색이다.
  • 스택을 이용하여 갈 수 있는만큼 최대한 많이 가고, 갈 수 없으면 스택에서 하나씩 빼서 이전 정점으로 돌아간다.
  1. 시작을 1로 시작한다. (보통 정점들이 숫자일 때, 작은 숫자가 우선적으로 탐색되곤 한다.)
     
  2. 현재 정점을 2로 옮긴다. 그러면, 순서가 1,2로 탐색한 것이 되고, 스택에는 [1,2] 가 들어가게 된다. (check[2] 에도 2를 탐색하였다는 의미로 1의 값을 넣는다.)
  3. 현재 정점을 3으로 옮긴다. 그러면 순서가 1,2,3으로 탐색한 것이 되고, 스택에는 [1,2,3] 이 들어가게 된다. (check[3] 에도 3을 탐색하였다는 의미로 1의 값을 넣는다.)
  4. 같은 방법으로 정점을 4로 옮긴다.
     
  5. 같은 방법으로 정점을 5로 옮긴다.
  6. 5에서는 연결된 정점들이 더 이상 갈 곳이 없다. 따라서, 현재 스택 상태인 [1,2,3,4,5] 에서 5를 pop하여 4로 돌아간다. (연결된 정점 i의 check[i] 를 확인해보았을 때 전부, 1로 확인된 후이므로, 더이상 탐색할 수 없다.)
     
  7. 4와 연결된 정점 중, 체크가 되어있지 않은 정점은 6뿐이므로, 현재 탐색 정점을 6으로 옮긴다.
  8. 6에서 갈 수 있는 곳이 없기 때문에 현재 스택 상태인 [1,2,3,4,6] 에서 6을 pop한다.
  9. 4에서 갈 수 있는 곳이 없기 때문에, 현재 스택 상태인 [1,2,3,4] 에서 4를 pop한다.
  10. 같은 방식으로 스택에 있는 모든 정점을 pop한다.

 

• BFS : Breadth First Search 로, 너비 우선 탐색이다.
  큐를 이용해 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식으로, 큐에 넣을 때 방문했다고 체크가 필요하다.
  1. 탐색은 1부터 시작한다. 1을 큐에 넣고, check[1] 의 값을 1로 바꾼다.
  2. 1과 연결된 모든 정점을 큐와 탐색 순서에 추가한다. [1,2,5]가 큐의 상태가 되고, 1은 연결된 모든 정점을 추가하였으므로, 큐에서 제거한다.
  3. 현재 큐의 상태가 [2,5]이므로, 2와 연결된 정점들을 추가한다. 5는 이미 체크가 된 상태이므로, 3을 추가하고 2를 제거한다.
     
  4. 현재 큐의 상태가 [5,3]이므로, 5와 연결된 정점 중, 체크가 되지않은 정점인 4를 큐에 추가하고, 5를 제거한다.
  5. 현재 큐의 상태가 [3,4]이다. 3과 연결된 모든 정점은 체크가 되어있으므로, 3을 제거한다.
  6. 현재 큐의 상태가 [4]이다. 4와 연결된 6을 큐에 추가하고, 4를 제거한다.
  7. 현재 큐의 상태가 [6]이다. 6과 연결된 정점이 없으므로, 6을 제거한다.
     

Kotlin 으로 구현된 알고리즘은 복습 문제 1260번을 참고

연결 요소 (Connected Component)

그래프의 모든 요소가 연결되어있지 않은 경우가 존재할 수 있다. 이렇게 나누어진 각각의 그래프를 연결 요소라고 한다. 아래와 같이 연결 요소에 는 속한 모든 정점을 연결하는 경로가 있어야며, 또 다른 연결 요소와 연결하는 경로가 있으면 안된다.

연결요소를 구하는 것은 DFS나 BFS 탐색을 이용해 구할 수 있다.
(예시로, 특정 정점을 이용한 DFS/BFS 탐색이 완료되었는데 정점이 남아있을 경우, 남아있는 다른 정점으로 DFS/BFS 탐색을 한다. check 하는 값을 1이 아닌 값을 늘리는 방식으로 몇개의 연결요소가 존재하는지 알 수 있을 것이다.)

이분 그래프 (Bipartie Graph)

그래프를 다음과 같이 A/B로 나눌 수 있으면 이분 그래프라고 한다.

)
A측에 포함되어있는 정점끼리 연결된 간선이 존재하지 않음.
B측에 포함되어있는 정점끼리 연결된 간선이 존재하지 않음.
모든 간선의 한 끝점은 A에 다른 끝점은 B를 향해 있음.

BFS/DFS 를 사용해 노드를 한번씩만 방문하면서, 인접노드를 현재 노드와 다른 값으로 check할 수 있으면 된다. (0,1 로 체크값을 지정한다.)

관련 문제는 1707번이나, 따로 직접 풀지 않았으므로 이분그래프 (1707번) 관련 풀이를 참고

순열 사이클

순열이 주어졌을 때, 순열 사이클의 개수를 찾는 문제의 경우 DFS를 이용해 이미 방문했던 수를 방문하게되면 순열 사이클이 존재한다는 의미가 되므로, return 하는 방식으로 풀 수 있다.

플러드 필 (Flood Fill)

어떤 위치와 연결된 모든 위치를 찾는 알고리즘으로, 행렬로 제공된 데이터에서 어떻게 서로 이어져있는지 찾는 문제형식이다.

단지번호붙이기 (2667번)과 아래 복습 문제의 다리 만들기 (2146번)을 참고.

복습 문제

DFS와 BFS(1260번)

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, m ,v) = readLine().split(" ").map { it.toInt() }

    val graph = Array(n + 1) { mutableListOf<Int>() }
    for (count in 1..m) {
        val (e1, e2) = readLine().split(" ").map { it.toInt() }
        graph[e1].add(e2)
        graph[e2].add(e1) //그래프는 양방향 그래프

    }
    println(dfs(graph, n, v))
    println(bfs(graph, n, v))
}

fun bfs(graph: Array<MutableList<Int>>, n: Int, v: Int) : String {
    graph.forEach {
        it.sort()
    }
    var result = "$v"
    val queue = mutableListOf<Int>()
    val check = Array(n + 1) { false }
    queue.add(v)
    check[v] = true

    while(queue.isNotEmpty()) {
        val current = queue.removeFirst()
        graph[current].forEach {
            if (!check[it]) {
                queue.add(it)
                result += " $it"
                check[it] = true
            }
        }

    }

    return result
}

fun dfs(graph: Array<MutableList<Int>>, n: Int, v: Int) : String {
    graph.forEach {
        it.sortDescending()
    }
    var result = "$v"
    val stack = mutableListOf<Int>() //sequence
    val check = Array(n + 1) { false }
    stack.add(v)
    check[v] = true

    while(stack.isNotEmpty()) {
        val current = stack.removeLast()
        if (!check[current] && current != v) {
            result += " $current"
            check[current] = true
        }
        graph[current].forEach {
            if (!check[it]) {
                stack.add(it)
            }
        }
    }

    return result
}