• BFS는 최단거리 보장 알고리즘이다.

1. 에라토스테네스의 체

import java.io.BufferedReader
import java.io.InputStreamReader

val MAX = 1_000

fun main(args: Array<String>) {
    // 1. 배열을 생성하여 초기화한다.
    var array: MutableList<Int> = MutableList<Int>(MAX + 1){ it }

    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
    // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
    for(i in 2..MAX){

        // 이미 지워진 수라면 건너뛰기
        if(array[i] == 0)
            continue

        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        for(j in i * 2 .. MAX step(i))
            array[j] = 0
    }

    array[1] = 0

    // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
    for(i in 2..MAX){
        if(array[i] != 0)
            print("${array[i]} ")
    }

}

2. 에라토스테네스의 체 (개선버전?)

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

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    var sb = StringBuilder();

    var M = st.nextToken().toInt()
    var N = st.nextToken().toInt()
    var arr = Array(N+1, {false})
    arr[0] = true; arr[1] = true;

    for(i in 2.. Math.sqrt(N+1.toDouble()).toInt()) {
        if(arr[i] == true) {
            continue;
        }

        for(j in i*i..N step +i) {
            arr[j] = true;
        }
    }

    for(i in M..N) {
        if(arr[i] == false) {
            sb.append(i).append('\\n')
        }
    }

    print(sb)
} // End of main

3. 코틀린의 2차원 배열(방법 1)

import java.io.*

fun main(args: Array<String>){
    val br = BufferedReader(InputStreamReader(System.`in`))
    var (size, count) = br.readLine().split(" ").map { it.toInt() }
    var array = Array(size) { ArrayList<Int>(size) }

    repeat(size){ index ->
        val elements = br.readLine().split(" ").map { it.toInt() }
        array[index].addAll(elements)
    }

    array.forEach {
        it.forEach {
            print("$it ")
        }
        println()
    }

}

4. DFS(가장 기초적인?) - 백준 24479

import java.io.*
import java.lang.StringBuilder

var visitedArr = mutableListOf<Int>()
var seq = 0

fun main(args: Array<String>) {

    val br = BufferedReader(InputStreamReader(System.`in`))
    var (n, m, r) = br.readLine().split(" ").map { it.toInt() }
		
		// 행렬로 구현
    var dfsMat = Array(n) { Array(n) { 0 } }
    var sb = StringBuilder()

    for (i in 0 until m) {
        var (start, end) = br.readLine().split(" ").map { it.toInt() }
        dfsMat[start - 1][end - 1] = 1
        dfsMat[end - 1][start - 1] = 1
    }

    visitedArr = MutableList<Int>(n) { 0 }

    dfs(dfsMat, r - 1)

    visitedArr.forEach {
        sb.append(it).append("\\n")
    }

    println(sb)
}

fun dfs(mat: Array<Array<Int>>, r: Int) {
    visitedArr[r] = ++seq

    for (i in 0 until visitedArr.size) {
        if(mat[r][i] == 1 && visitedArr[i] == 0)
            dfs(mat, i)
    }

}

5. DFS(보완된 버전) - 백준 24479

var visited = intArrayOf()
var order = 0

fun main() {
    val inputs = readln().split(" ").map{ it.toInt() }
    val pointCount = inputs[0]
    val lineCount = inputs[1]
    val startPoint = inputs[2] - 1
    val lines = Array<MutableList<Int>>(pointCount) { mutableListOf() }

    repeat(lineCount) {
        readln().split(" ").map { it.toInt() - 1 }.let {
            lines[it.first()].add(it.last())
            lines[it.last()].add(it.first())
        }
    }
    lines.forEach { it.sort() }

    visited = IntArray(pointCount) { order }

    dfs(lines, startPoint)

    visited.forEach { println(it) }
}

fun dfs(lines: Array<MutableList<Int>>, startPoint: Int) {
    visited[startPoint] = ++order
    lines[startPoint].forEach {
        if(visited[it] == 0) dfs(lines, it)
    }
}