[백준][Kotlin] DFS와 BFS - 1260번

문제 링크 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 복사

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

예제 출력 1 복사

1 2 4 3
1 2 3 4

---

지금까지 절차지향으로만 풀어왔는데, 완벽하진 않으나, 객체지향을 도입하여 풀어보기로 한다.

먼저, 정점을 가지는 Vertex 라는 클래스로 정의하여 

• num : 몇 번째 정점
• check : 방문 여부
• neighbors : 이웃한 정점 목록

을 나타내며, 해당 정점을 방문할 때 사용되는 visit() 메서드와, 인접한 정점을 연결하는 connect() 메서드를 갖는다.

 

DFS / BFS 로직은 일반적이다.

코드

import java.util.*
import java.util.stream.IntStream

fun main() {
    val (vertexCount, edgeCount, startNum) = readLine()?.split(' ')!!
        .map { it.toInt() }
        .take(3)

    val originalVertexList: List<Vertex> = getVertexList(vertexCount, edgeCount)

    println(DFS(startNum, originalVertexList.map { it.copy() }).joinToString(" "))
    println(BFS(startNum, originalVertexList.map { it.copy() }).joinToString(" "))
}

private fun getVertexList(
    vertexCount: Int,
    edgeCount: Int,
): List<Vertex> {
    val originalVertexList: List<Vertex> = IntStream.rangeClosed(0, vertexCount)
        .toArray()
        .map { Vertex(it) }

    for (i in 0 until edgeCount) {
        val (vertex1, vertex2) = readLine()?.split(' ')!!
            .map { it.toInt() }
            .take(2)

        originalVertexList[vertex1].connect(vertex2)
        originalVertexList[vertex2].connect(vertex1)
    }

    originalVertexList.forEach { it.neighbors.sort() }

    return originalVertexList
}

data class Vertex(
    val num: Int,
    var check: Boolean = false,
    val neighbors: MutableList<Int> = mutableListOf(),
) {
    fun visit() {
        if (check) {
            throw IllegalStateException("$num's check is true.")
        }
        check = true
    }

    fun connect(neighbor: Int) {
        neighbors.add(neighbor)
    }
}

fun BFS(startVertex: Int, vertexList: List<Vertex>): List<Int> {
    val queue = LinkedList<Int>()
    val result = mutableListOf(startVertex)

    vertexList[startVertex].visit()
    queue.add(startVertex)

    while (!queue.isEmpty()) {
        val (_, _, neighbors) = vertexList[queue.remove()]

        neighbors.forEach {
            if (!vertexList[it].check) {
                vertexList[it].visit()
                result.add(it)
                queue.add(it)
            }
        }
    }

    return result
}

fun DFS(startVertex: Int, vertexList: List<Vertex>): List<Int> {
    val result = mutableListOf(startVertex)
    val current: Vertex = vertexList[startVertex]

    current.visit()

    current.neighbors.forEach {
        if (!vertexList[it].check) {
            result += DFS(it, vertexList)
        }
    }

    return result
}