[백준] 경로 찾기 (11403)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/11403

문제 참고(플로이드 와샬) : https://6a68.tistory.com/13

문제 참고(DFS) : https://gist.github.com/jayden-lee/d7b858b63319b65ef2c8b2fef43d4f7b

문제 참고(BFS) : https://hees-dev.tistory.com/21

 

<첫번째> 플로이드 와샬

import java.io.*
import java.util.*

var size: Int = 0
var route: Array<IntArray> = arrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    size = readLine().toInt()
    route = Array( size ) { IntArray( size ) }

    for ( i in 0 until size ) {
        val str = readLine().split(" ")
        for ( j in  0 until size ) {
            route[i][j] = (str[j] + "").toInt()
        }
    }

    floydWarshall()

}

fun floydWarshall() {

    for ( k in 0 until size ) {
        for ( i in 0 until size ) {
            for ( j in 0 until size ) {
                if ( route[i][k] == 1 && route[k][j] == 1)
                    route[i][j] = 1
            }
        }
    }


    for ( i in 0 until size ) {
        for ( j in 0 until size ) {
            print("${route[i][j]} ")
        }
        println()
    }

}

 

<두번째> DFS

import java.io.*
import java.util.*

var vertex = 0
var originalMatrix: Array<IntArray> = arrayOf()
var visitedMatrix: Array<IntArray> = arrayOf()
var visitedVertex: BooleanArray = booleanArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    vertex = readLine().toInt()

    originalMatrix = Array( vertex ) { IntArray( vertex ) }
    visitedMatrix = Array( vertex ) { IntArray( vertex ) }
    visitedVertex = BooleanArray( vertex )

    for ( i in 0 until vertex ) {
        val str = readLine().split(" ")
        for ( j in 0 until vertex ) {
            originalMatrix[i][j] = (str[j] + "").toInt()
        }
    }

    for ( i in 0 until vertex ) {

        dfs( i )

        for ( j in 0 until vertex ) {
            if ( visitedVertex[j] ) {
                visitedMatrix[i][j] = 1
            }
        }

        Arrays.fill(visitedVertex, false)
    }

    print()
}

fun dfs(startVertex: Int) {

    for ( i in 0 until vertex ) {
        if ( !visitedVertex[i] && originalMatrix[startVertex][i] == 1 ){
            visitedVertex[i] = true
            dfs(i)
        }
    }

}

fun print() {

    for ( i in 0 until vertex ) {
        for ( j in 0 until vertex ) {
            print("${visitedMatrix[i][j]} ")
        }
        println()
    }
}

 

<세번째> BFS

import java.io.*
import java.util.*

var matrix: Array<IntArray> = arrayOf()
var queue: Queue<Int> = LinkedList<Int>()
var vertex: Int = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    vertex = readLine().toInt()
    matrix = Array( vertex ) { IntArray( vertex ) }

    for ( i in 0 until vertex ) {
        val str = readLine().split(" ")
        for ( j in 0 until vertex ) {
            matrix[i][j] = (str[j]+"").toInt()
        }
    }

    for ( i in 0 until vertex ) {
        for ( j in 0 until vertex ) {
            if ( matrix[i][j] == 1 )
                queue.add(j)
        }

        while ( !queue.isEmpty() ) {
            val dest = queue.poll()
            bfs( i, dest )
        }
    }

    print()

}


fun bfs(start: Int, dest: Int) {
    matrix[start][dest] = 1

    for ( i in 0 until vertex ) {
        if (matrix[dest][i] == 1 && matrix[start][i] == 0 )
            queue.add(i)
    }
}

fun print() {

    for ( i in 0 until vertex ) {
        for ( j in 0 until vertex ) {
            print("${matrix[i][j]} ")
        }
        println()
    }
}