#1260 DFS와 BFS

문제

---

 

 

코드

---

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m, v) = readLine().split(' ').map { it.toInt() }
    val edges = Array<MutableList<Int>>(n + 1) { mutableListOf() }
    val isVisited = Array(n + 1) { false }
    val q: Queue<Int> = LinkedList()
    repeat(m) {
        val (start, end) = readLine().split(' ').map { it.toInt() }
        edges[start].add(end)
        edges[end].add(start)
    }
    for (list in edges) {
        list.sort()
    }

    fun dfs(start: Int) {
        print("$start ")
        isVisited[start] = true
        for (next in edges[start]) {
            if (!isVisited[next]) {
                dfs(next)
            }
        }
    }

    fun bfs(start: Int) {
        q.add(start)
        isVisited[start] = true
        while (q.isNotEmpty()) {
            for (next in edges[q.peek()]){
                if (!isVisited[next]) {
                    q.add(next)
                    isVisited[next] = true
                }
            }
            print("${q.poll()} ")
        }
    }

    dfs(v)
    isVisited.fill(false)
    println()
    bfs(v)
}

 

풀이

---

dfs, bfs를 전부 까먹어서..

백트래킹 문제를 풀어보려고 하는데 전혀 풀지를 못하겠더라ㅋㅋ

그래서 그래프 탐색 기초부터 풀어봤다..

 

처음에 정점 번호가 작은 것부터 순회하라고 해서 edge 리스트의 자료형을 우선순위 큐로 뒀다

이유는 리스트를 정렬하기 싫어서..

 

근데 예제들은 전부 정상적으로 동작하는데, 문제를 제출하니까 틀렸다고 나오더라

게시판에서 반례를 찾아서 전부 돌려보는데 다른 예제들은 전부 정답이 출력되는데

아래 예제에서 문제가 발생했다.

 

잘못된 코드

import java.util.*

fun main() = with(System.in.bufferedReader()) {
    val (n, m, v) = readLine().split(' ').map { it.toInt() }
    val edges = Array<PriorityQueue<Int>>(n + 1) { PriorityQueue() }
    val isVisited = Array(n + 1) { false }
    val q: Queue<Int> = LinkedList()
    repeat(m) {
        val (start, end) = readLine().split(' ').map { it.toInt() }
        edges[start].add(end)
        edges[end].add(start)
    }

    fun dfs(start: Int) {
        print("$start ")
        isVisited[start] = true
        for (next in edges[start]) {
            if (!isVisited[next]) {
                dfs(next)
            }
        }
    }

    fun bfs(start: Int) {
        q.add(start)
        isVisited[start] = true
        while (q.isNotEmpty()) {
            for (next in edges[q.peek()]){
                if (!isVisited[next]) {
                    q.add(next)
                    isVisited[next] = true
                }
            }
            print("${q.poll()} ")
        }
    }

    dfs(v)
    isVisited.fill(false)
    println()
    bfs(v)
}

정답 코드와 다른 점은 edges의 자료형이 변경되었음

그리고 정답 코드에서는 List의 정렬 반복문이 추가되었음

 

반례

5 8 1
1 2
3 1
4 1
1 5
2 5
5 3
3 4
4 2

 

정답

1 2 4 3 5 
1 2 3 4 5

 

잘못된 출력

1 2 5 3 4
1 2 3 4 5

 

이유를 찾아보니, 우선순위 큐는 힙(Heap)구조를 가짐

힙은 완전 이진 트리 형태를 가지며, 최소 힙과 최대 힙 두 종류가 있음

우선순위 큐는 기본적으로 최소 힙으로 구현되어있음

힙은 정렬된 배열이 아니라, 트리 구조로 요소를 배치하기 때문에 내부적으로 모든 요소들이 항상 오름차순 정렬되어있지 않음!!

대신 힙의 루트 노드가 항상 최소값 또는 최대값을 가지게 되는 구조!(최소 힙의 경우 최소값, 최대 힙의 경우 최대값)

따라서 우선순위 큐는 최소 힙의 구조를 가지기 때문에 부모 노드는 자식 노드보다 작은 값을 가지지만, 같은 레벨에서는 정렬이 되지 않음

 

오류가 발생했던 이유가 우선순위 큐의 top(peek)는 항상 작은 요소를 반환하지만, 전체적인 순서는 보장하지 않기 때문이다

그래서 우선순위 큐 대신 리스트를 사용해서 직접 정렬을 해주는 것으로 해결했다.

 

우선순위 큐를 함부로 사용하면 안되겠다고 느낀다..

정말 필요한 곳에서만 사용하도록 하자