[백준 kotlin] 1260 DFS와 BFS

서론

코딩테스트 언어를 파이썬에서 코틀린으로 변경하였다. 가장큰 이유는 바로 안드로이드 직군에서 kotlin코테를 더 많이 본다는점...

코틀린과 파이썬의 문법은 천차만별이고 문법을 익힐 필요가 있기 때문에 이미 풀어본 문제들을 코틀린을 사용해서 다시 해결하였다.

문제

DFS및 BFS를 이용하여 문제를 해결한다.

---

풀이

기본적인 구현은 간단하기 때문에 사용한 문법을 정리하면서 알아본다.

var graph = arrayOf<IntArray>()
var visited = booleanArrayOf()
var dfsAns = ArrayList<String>()
var bfsAns = ArrayList<String>()

먼저 필요한 전역변수들을 선언한다.

그래프와 방문여부를 담을 변수, 정답을 출력할 변수이다.

fun solve() = with(BufferedReader(InputStreamReader(System.`in`))) {
        val str = readLine().split(" ")
        val N = str[0].toInt()
        val M = str[1].toInt()
        val V = str[2].toInt()

문제를 해결할 solve함수이다. 

입력시간을 최소화 하기위해 BufferedReader를 사용하였다.

이후 N M V 를 입력받기위해 str을 사용하였고 str의 각 위치에서 N M V를 추출하였다.

 

graph = Array(N) {IntArray(N)}
visited = BooleanArray(N)

그래프의와 visited의 크기를 지정하였다.

 

repeat(M) {
    val (x, y) = readLine().split(" ").map { it.toInt() }
    graph[x - 1][y - 1] = 1
    graph[y - 1][x - 1] = 1
}

repeat는 해당 숫자만큼 반복한다는 뜻이다.

x, y 를 int값으로 입력받아주었고, 이 값들을 graph에 입력시켰다.

 

다음은 DFS의 구현이다.

fun DFS(n: Int, v: Int) {
    var ans = ArrayList<String>()
    visited[v] = true
    dfsAns.add((v + 1).toString())

    for (i in 0 until n) {
        if ( graph[v][i] == 1 && !visited[i]) DFS(n, i)
    }
}

visited 값을 true로 초기화시키고

dfsAns값에 현재 간선의 위치를 입력시킨다.

 

다음으로 조건을 확인한 후 DFS를 재귀한다.

 

fun BFS(n: Int, v: Int) {
        val list = LinkedList<Int>()

        list.add(v)
        visited[v] = true
        bfsAns.add((v + 1).toString())

        while (list.isNotEmpty()) {
            val cur = list.poll()

            for (i in 0 until n) {
                if (graph[cur][i] == 1 && !visited[i]) {
                    list.add(i)
                    visited[i] = true
                    bfsAns.add((i + 1).toString())

                }
            }
        }
    }

BFS의 구현은 다음과 같다.
먼저 linkedlist는 queue로 사용하였다.

큐에 현재 간선을 입력시키고

방문하였으므로 ans값을 추가시킨다.

 

그 후 큐가 빌때까지 while문을 돌린다.

여기서는 큐에서 원소를 꺼내기 위해 poll을 사용하였는데 remove()와의 차이점은 null exeception을 지원하냐이다.

이 후 graph[cur]에 연결되어있는 원소를 탐색하며 정답에 입력한다.

 

visited.fill(false)
DFS(N, V - 1)
visited.fill(false)
BFS(N, V - 1)
println(dfsAns.joinToString(" "))
println(bfsAns.joinToString(" "))

다시 solve함수에서 DFS와 BFS를 시행하기전에 visited값을 false로 초기화시킨다.

이 후 함수를 실행한 후 출력한다.

abcdabc패턴에 대해서는 다음과 같이 lps배열이 만들어진다.

해당 과정을 코드로 나타내면 다음과 같다.

 

 

---

코드

import java.io.*
import java.util.*
import kotlin.collections.ArrayList


class Solution {
    var graph = arrayOf<IntArray>()
    var visited = booleanArrayOf()
    var dfsAns = ArrayList<String>()
    val bfsAns = ArrayList<String>()
    fun solve() = with(BufferedReader(InputStreamReader(System.`in`))) {
        val str = readLine().split(" ")
        val N = str[0].toInt()
        val M = str[1].toInt()
        val V = str[2].toInt()

        graph = Array(N) {IntArray(N)}
        visited = BooleanArray(N)

        repeat(M) {
            val (x, y) = readLine().split(" ").map { it.toInt() }
            graph[x - 1][y - 1] = 1
            graph[y - 1][x - 1] = 1
        }

        visited.fill(false)
        DFS(N, V - 1)
        visited.fill(false)
        BFS(N, V - 1)
        println(dfsAns.joinToString(" "))
        println(bfsAns.joinToString(" "))


    }

    fun DFS(n: Int, v: Int) {
        var ans = ArrayList<String>()
        visited[v] = true
        dfsAns.add((v + 1).toString())

        for (i in 0 until n) {
            if ( graph[v][i] == 1 && !visited[i]) DFS(n, i)
        }
    }

    fun BFS(n: Int, v: Int) {
        val list = LinkedList<Int>()

        list.add(v)
        visited[v] = true
        bfsAns.add((v + 1).toString())

        while (list.isNotEmpty()) {
            val cur = list.poll()

            for (i in 0 until n) {
                if (graph[cur][i] == 1 && !visited[i]) {
                    list.add(i)
                    visited[i] = true
                    bfsAns.add((i + 1).toString())

                }
            }
        }
    }
}

fun main() {
    val solution = Solution()
    solution.solve()
}