[ 알고리즘 ] 그래프 & DFS , BFS

 

인접행렬에 대한 탐색문제에서 대표적으로 쓰이는 DFS 와 BFS 를 정리해보고자 합니다.

처음에는 DFS , BFS 의 구현에 있어서 잘 이해가 되지 않았지만 틀을 외워서 사용하다 보니 잘 이해가 되었습니다. 저와 같은 분이 계시다면 이 방법을 추천드립니다!!

 

공통

• 간선의 데이터를 자료형에 맞게 저장할 수 있어야합니다.
  • 이차원 배열 형태
  • 이차원 배열 + 내부적으로 mutablelis
• 필요에 따라서 방문한 위치를 표시 할 수 있어야 합니다.
  • 위에서 저장한 이차원 배열을 수정 할 수 도 있음
  • 따로 행렬을 만들어 관리 할 수 도 있음

 

BFS

• 너비 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다.
• 자식 노드보다 형제 노드를 우선적으로 방문한다는 특징을 가진다.
• 구현의 핵심은 방문할 리스트를 생성하고 방문할 리스트를 Queue 형태로 관리한다.
• Queue에 원소가 다할때 까지 while 문을 돌린다.
• 한 노드에 연결된 다른 노드들을 찾기위해 포문을 돌린다.
• 방문 노드에 대한 처리는 Queue 에서 빼는 순간이 아닌 넣는 순간에 한다.
  • 빼는 순간 처리하더라도 정답이지만 메모리, 시간 낭비가 발생할 수 있다.

DFS

• 깊이 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다.
• 형제 노드 보다 자식 노드를 우선적으로 방문한다는 특징을 가진다.
• 구현의 핵심은 제귀를 통해서 구현한다.
• 한 노드에 연결된 다른 노드를 찾기 위해 포문을 돌린다.

 

😃예제 : 백준 1260 (kotlin 풀이)

 

1. 문제 설명 

본 문제는 인접 행렬이 주어지고 DFS , BFS 에 맞게 방문하는 Node 를 출력하는 문제 입니다.

 

다른 그래프 문제의 경우 checkArray를 따로 만들지 않고 한번 거쳐간 곳을 없는 경로( 0 값으로 대체)로 만들어 풀 수 도 있지만 한 문제에 2개의 탐색을 적용하기 위해 데이터의 훼손을 막고자 checkArray를 사용했습니다.

 

 

2.  DFS 

•  깊이 우선 탐색으로 재귀를 통해서 구현할 수 있다.
•  여러 node가 연결 되었을때 연결된 노드의 정렬이 필요하므로 인접행렬은 배열 안에 mutableList 로 구현
•  노드에 연결된 노드를 순회하면서 제귀의 인자로 넣어준다

fun dfs(node: Int) {
    checkArray[node] = 1
    sb.append("$node ")
    val temp = matrixEdge[node].sorted()
    temp.forEach { if (checkArray[it] == 0) dfs(it) }
}

 

 

3. BFS

• 넓이 우선 탐색으로서 queue 를 이용한다.
• 포문을 돌며 queue 에 추가함으로서 넓이를 먼저 탐색한다.

fun bfs(node: Int) {
    val queue = LinkedList<Int>()
    checkArray[node] = 1
    queue.add(node)
    sb.append("$node ")


    while (queue.isNotEmpty()) {
        val newNode = queue.poll()

        matrixEdge[newNode].sorted().forEach {
            if (checkArray[it] == 0) {
                checkArray[it] = 1
                queue.add(it)
                sb.append("$it ")
            }
        }
    }

 

 

4. 전체

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var matrixEdge: Array<MutableList<Int>>
val sb: StringBuilder = StringBuilder()
lateinit var checkArray: Array<Int>


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine(), " ")

    val N = st.nextToken().toInt()
    val M = st.nextToken().toInt()
    val V = st.nextToken().toInt()

    matrixEdge = Array(N + 1) { mutableListOf() }

    // 지나친 노드 확인
    checkArray = Array<Int>(N + 1) { 0 }

    // 경로 matrix 세팅
    repeat(M) {
        val nodes = readLine().split(" ").map { it.toInt() }
        matrixEdge[nodes[0]].add(nodes[1])
        matrixEdge[nodes[1]].add(nodes[0])
    }

    dfs(V)
    println(sb)

    checkArray = Array<Int>(N + 1) { 0 }
    sb.clear()

    bfs(V)
    println(sb)
}


fun dfs(node: Int) {
    checkArray[node] = 1
    sb.append("$node ")
    val temp = matrixEdge[node].sorted()
    temp.forEach { if (checkArray[it] == 0) dfs(it) }
}

fun bfs(node: Int) {
    val queue = LinkedList<Int>()
    checkArray[node] = 1
    queue.add(node)
    sb.append("$node ")


    while (queue.isNotEmpty()) {
        val newNode = queue.poll()

        matrixEdge[newNode].sorted().forEach {
            if (checkArray[it] == 0) {
                checkArray[it] = 1
                queue.add(it)
                sb.append("$it ")
            }
        }
    }
}