[백준] 1260 (DFS와 BFS)

#1 알고리즘

DFS 및 BFS 알고리즘을 알고 있는지 묻는 간단한 문제다. 하지만, 약간 신경 쓸 점이 3가지 있다.
 
1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
인접 배열을 정렬하면 된다. 나는 퀵 정렬을 이용했다.

2. 정점의 개수 N(1 ≤ N ≤ 1,000)
문제에서 출제되는 정점은 1부터 시작한다. 즉, 1-based indexing을 사용하고 있다. 나는 이 문제를 풀기 위해 예전에 정리해 게시글로 남겨두었던 BFS 및 DFS 알고리즘 코드를 그대로 가져다 쓸 건데, 문제는 해당 코드들은 정점이 0부터 시작한다는 조건 하에 짜여진 코드들이다. 즉, 정점이 0-based indexing을 사용하고 있다. 이 차이를 해소하기 위해서 '인접 배열들의 리스트(listOfAdjacencyArray)'의 첫 원소로 사용하지 않을 더미 배열을 넣어주었다 (#3의 코드 참조). 이러면 '인접 배열들의 리스트(listOfAdjacencyArray)'의 인덱스 번호와 정점 번호가 정확히 일치하게 된다. 즉, "어떤 정점 n의 인접 배열은 listOfAdjacencyArray[n]이다"라고 말할 수 있게 된다.

3. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다
인접 배열을 만들기 위해서 원소들을 채워나갈 때, 이미 존재하는 원소가 있는 지 검사하는 코드를 넣으면 된다.

#2 코드 - 코틀린

import java.util.*

val listOfAdjacencyArray: MutableList<ArrayList<Int>> = mutableListOf()

fun main() {
    val information = readln().split(" ")
    val vertexCount = information[0].toInt()
    val edgeCount = information[1].toInt()
    val startVertex = information[2].toInt()

    // (1) listOfAdjacencyArray[0] 추가. 그러나 사용하지 않을 것임
    listOfAdjacencyArray.add(arrayListOf())

    // 실제로 사용할 listOfAdjacencyArray[1] 부터 추가
    for (i: Int in 0..<vertexCount) {
        listOfAdjacencyArray.add(arrayListOf())
    }

    // (2) 인접 배열에 원소 넣기
    for (i: Int in 0..<edgeCount) {
        val vertexes = readln().split(" ")
        val vertexA = vertexes[0].toInt()
        val vertexB = vertexes[1].toInt()

        if (vertexB !in listOfAdjacencyArray[vertexA]) {
            listOfAdjacencyArray[vertexA].add(vertexB)
        }

        if (vertexA !in listOfAdjacencyArray[vertexB]) {
            listOfAdjacencyArray[vertexB].add(vertexA)
        }
    }

    // (3) 인접 배열 오름차순으로 정렬
    for (adjacencyArray in listOfAdjacencyArray) {
        quickSort(adjacencyArray, 0, adjacencyArray.size - 1)
    }

    // (4) DFS 수행
    val discovered = mutableSetOf<Int>()
    dfs(listOfAdjacencyArray, startVertex, discovered)

    println()

    // (5) BFS 수행
    bfs(listOfAdjacencyArray, startVertex)
}

fun quickSort(array: ArrayList<Int>, startIndex: Int, endIndex: Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if (startIndex < endIndex) {
        val pivotIndex = partitionAroundPivot(array, startIndex, endIndex)
        quickSort(array, startIndex, (pivotIndex - 1))
        quickSort(array, pivotIndex, endIndex)
    }
}

// endIndex가 pivot(기준)의 역할 수행
fun partitionAroundPivot(array: ArrayList<Int>, startIndex: Int, endIndex: Int): Int {
    var endOfLower = startIndex - 1

    for (i: Int in startIndex..<endIndex) {
        if (array[i] <= array[endIndex]) {
            // array[endIndex]보다 lower인 값 저장할 공간 확보를 위해 endOfLower++
            endOfLower++

            // array[i]와 array[endOfLower]의 값 서로 교환
            val temp = array[endOfLower]
            array[endOfLower] = array[i]
            array[i] = temp
        }
    }

    // array[endOfLower] 바로 뒤에 array[endIndex] (= 기준) 값이 오게 하기 위해서 endOfLower++
    endOfLower++

    // array[endIndex]과 array[endOfLower]의 값 서로 교환
    val temp = array[endOfLower]
    array[endOfLower] = array[endIndex]
    array[endIndex] = temp

    return endOfLower
}

fun dfs(listOfAdjacencyArray: List<ArrayList<Int>>, vertex: Int, discovered: MutableSet<Int>) {
    discovered.add(vertex)
    print("$vertex ")

    for (neighborVertex in listOfAdjacencyArray[vertex]) {
        if (neighborVertex !in discovered) {
            dfs(listOfAdjacencyArray, neighborVertex, discovered)
        }
    }
}

fun bfs(listOfAdjacencyArray: List<ArrayList<Int>>, startVertex: Int) {
    val queue: Queue<Int> = LinkedList()
    val discovered = mutableSetOf<Int>()

    queue.add(startVertex)
    discovered.add(startVertex)

    while (queue.isNotEmpty()) {
        val vertex = queue.remove()
        print("$vertex ")

        for (neighborVertex in listOfAdjacencyArray[vertex]) {
            if (neighborVertex !in discovered) {
                queue.add(neighborVertex)
                discovered.add(neighborVertex)
            }
        }
    }
}