ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [ 알고리즘 ] 그래프 & DFS , BFS
    자료구조 & 알고리즘/알고리즘 2022. 3. 8. 00:49

     

    인접행렬에 대한 탐색문제에서 대표적으로 쓰이는 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 ")
                }
            }
        }
    }

    댓글

Designed by Tistory.