[BOJ] 2667번 : 단지번호붙이기

문제 보기

kotlin

BFS를 이용한 풀이

import java.util.*

var n = 0
var answer = mutableListOf<Int>()
val dx = intArrayOf(1, 0, -1, 0)
val dy = intArrayOf(0, 1, 0, -1)
lateinit var map: Array<IntArray>
lateinit var visit: Array<BooleanArray>

fun main() {
    init()

    for (x in 0 until n) {
        for (y in 0 until n) {
            if (!visit[x][y] && map[x][y] == 1) {
                bfs(x, y)
            }
        }
    }

    println(answer.size)
    answer.sorted().forEach { println(it) }
}

fun bfs(x: Int, y: Int) {
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    var count = 0

    queue.offer(x to y)
    visit[x][y] = true

    while (queue.isNotEmpty()) {
        val cur = queue.poll()
        for (dir in 0 until 4) {
            val (nx, ny) = cur.first + dx[dir] to cur.second + dy[dir]

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
            if (visit[nx][ny] || map[nx][ny] == 0) continue

            visit[nx][ny] = true
            queue.add(nx to ny)
        }
        count++
    }
    answer.add(count)
}

fun init() = with(Scanner(System.`in`)) {
    n = nextInt()
    map = Array(n) { IntArray(n) }
    visit = Array(n) { BooleanArray(n) }

    for (i in 0 until n) {
        val line = next()
        for (j in 0 until n) {
            map[i][j] = line[j] - '0'
        }
    }
}

DFS를 이용한 풀이

import java.util.*

var n = 0
var count = 0
var answer = mutableListOf<Int>()
val dx = intArrayOf(1, 0, -1, 0)
val dy = intArrayOf(0, 1, 0, -1)
lateinit var map: Array<IntArray>
lateinit var visit: Array<BooleanArray>

fun main() {
    init()

    for (x in 0 until n) {
        for (y in 0 until n) {
            if (!visit[x][y] && map[x][y] == 1) {
                dfs(x, y)
                answer.add(count)
                count = 0
            }
        }
    }

    println(answer.size)
    answer.sorted().forEach { println(it) }
}

fun dfs(x: Int, y: Int) {
    visit[x][y] = true
    count++

    for (dir in 0 until 4) {
        val (nx, ny) = x + dx[dir] to y + dy[dir]
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
        if (visit[nx][ny] || map[nx][ny] == 0) continue

        dfs(nx, ny)
    }
}

fun init() = with(Scanner(System.`in`)) {
    n = nextInt()
    map = Array(n) { IntArray(n) }
    visit = Array(n) { BooleanArray(n) }

    for (i in 0 until n) {
        val line = next()
        for (j in 0 until n) {
            map[i][j] = line[j] - '0'
        }
    }
}