구름톤 3주차 코테풀이 수요일

발전기 문제

  • 발전기 문제는 전형적인 BFS 문제라고 생각했는데 왜냐하면…
    • 인접한 집은 전기가 통한다 » 인접노드를 먼저 탐색해라 » BFS
    • 발전기의 최소한의 갯수를 구해라 » BFS 의 EntryPoint 갯수 구하기 » 삼성코테 기출 / 백준 등등의 문제들 중에서 섬의 갯수 구하기 유형
  • 그런데 이제.. 조금 불평불만을 해보자면 글 읽기가 좀 힘든데 왜 그런고 하니
    • “빈땅” 에 발전기를 설치하는 경우 » 2^(N*N) 시간복잡도 만큼의 극한의 완전탐색 문제 » n=5 이면 2^25 만큼 시간복잡도 한계지점
    • “집” 에다가 발전기를 설치하는 경우 » 단순 BFS
  • 위 두 문장 사이가 뭔가 미묘하게 애매한 구석이 있어서 좀더 명시적으로 이야기되면 좋을꺼같습니다.

BFS DFS 이야기

  • BFS를 돌려야하는 경우
    • 큐로 도전 할만한 것들 / FIFO
    • 완전탐색, 방문이 가능한 모든 노드를 탐색, 크기 구하기 등의 유형이 대표적입니다
  • DFS를 돌려야하는경우
    • 스텍 자료구조로 도전할만한 것들 / FILO
    • 최단경로 등등..
  • 알고리즘 문제에서 완전탐색을 허용하는 경우에는 BFS 로 풀어도 되고 DFS 로 풀어도 되는데, 완탐을 허용하지 않는 경우에는 둘중 택1을 해야하는 경우도 있는거같습니다

이 문제를 풀며 느낀 코틀린 언어

  • 제가 자바로 코테언어를 돌리다가 최근에 코틀린으로 계속 풀고 있는데요
  • 자바로 코테를 푸는 아주 비효율적으로 푸는 사람도 적은데 코틀린을 쓰는 사람은 더 적을꺼같아서
  • 근데.. 그냥 파이썬으로 푸는게 좋은거같아요! 저도 파이썬으로 많이 풉니다. 기업코테에 언어 제한이 없으면 든든국밥 파이썬으로 풉니다

matrix 초기화

// 2차원 배열이 필요한 경우
val visited: MutableList<MutableList<Boolean>> = MutableList(sizeOfFirst) { MutableList(sizeOfSecond) { false } }
val countMatrix : MutableList<MutableList<Int>> = MutableList(sizeOfFirst) { MutableList(sizeOfSecond) { 0 } }

Column, Row 혼동

// Column, Row, X, Y, 등등.. 2차원 탐색을 하다보면 혼동이 많이되는데 그냥 First, Second 로 통일하고 Pair를 쓰면 편합니다
  • 자바는 아주 안타깝게도 Pair 자료구조가 없습니다 ㅠㅠ.. 그래서 우회방법 몇가지는
int[] pair = new int[] {first, second}
  • 이렇게 간이 Pair 자료구조를 만들어서 써도 됩니다
private class MyPair {
    final int first;
    final int second;
    public MyPair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}
  • 근데 그냥 파이썬을 쓰던가 진심모드로 알고리즘 하실꺼면 C++ 에서 진짜 Pair() 를 쓰는것도 좋아보입니다.. (왜 굳이 java에서)
  • 자랑은 아닌데.. 알고리즘에서만 허용되는 자바언어에서 금지된 기술
// 자바언어에서는 함수가 무조건 하나의 리턴값만을 갖는데, 함수 하나가 두가지를 리턴하도록 하는 금지된 기술
// SRP 위배가 명백해서 쓰면 안되지만... 일회용 코딩으로 제출하고 다시는 안볼 알고리즘에서는 가끔 써야하더라구요..
public Object[] doSomthing() {
    String name = "gilldong"
    Inteager age = 999
    return new Object[] {name,age}
}

코틀린을 위한 네이티브 큐는 없다

  • 이펙티브 코틀린이나, 코틀린 책 보면 코틀린 네이티브 SDK/API 쓰세요 라는 말이 많이 있어서, 자바에서 쓰던 스니펫들을 그대로 쓰기보다 코틀린 네이티브 API/SDK 가 있는지 한번 꼭 확인해보는데, Queue 는 그런게 없어서 자바에서 쓰던 그대로 사용해야 합니다 (아직은..)
val queue: Queue<Pair<Int, Int>> = LinkedList()// 자바의 그것을 사용해야한다

전체코드

package goormton

import java.util.*

val diffs: List<Pair<Int, Int>> = listOf(
    Pair(1, 0),
    Pair(-1, 0),
    Pair(0, 1),
    Pair(0, -1)
)
var count = 0

//0829
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val matrix: MutableList<MutableList<Int>> = readMatrix(N)
    val visited: MutableList<MutableList<Boolean>> = MutableList(N) { MutableList(N) { false } }

    for (fi in 0 until N) {
        for (si in 0 until N) {
            doBfs(fi, si, N, matrix, visited);
        }
    }
    println(count)
    //println("count = $count")
}

fun doBfs(
    fi: Int,
    si: Int,
    N: Int,
    matrix: MutableList<MutableList<Int>>,
    visited: MutableList<MutableList<Boolean>>,
) {

    if (isHouse(matrix, fi, si) && isNotVisited(visited, fi, si)) {

        val queue: Queue<Pair<Int, Int>> = LinkedList()// 자바의 그것을 사용해야한다
        queue.add(Pair(fi, si))
        visited[fi][si] = true

        while (queue.isNotEmpty()) {
            //printVisited(visited)
            val curCodi = queue.poll()
            //println(queue.size)
            //println(curCodi)

            for (step in diffs) {
                val nextCodi = Pair(
                    curCodi.first + step.first,
                    curCodi.second + step.second
                )
                if (isInRange(nextCodi, N) &&
                    isHouse(matrix, nextCodi.first, nextCodi.second) &&
                    isNotVisited(visited, nextCodi.first, nextCodi.second)
                ) {
                    //println("GO NEXT = $nextCodi")
                    queue.add(nextCodi)
                    visited[nextCodi.first][nextCodi.second] = true
                }
            }
        }
        count += 1
    }
}

fun printVisited(visited: MutableList<MutableList<Boolean>>) {
    visited.forEach { it ->
        it.forEach {
            if (it) {
                print("■  ")
            } else {
                print("□  ")
            }
        }
        println()
    }
}

fun configMatrix(N: Int): MutableList<MutableList<Boolean>> {
    val s: MutableList<MutableList<Boolean>> = mutableListOf()
    //return MutableList(N) { MutableList(N) { false } }
    for (i in 0 until N) {
        val ss: MutableList<Boolean> = MutableList(N) { false }
        s.add(ss)
    }
    return s
}

fun isInRange(nextCodi: Pair<Int, Int>, size: Int): Boolean {
    return (nextCodi.first in 0 until size) &&
            (nextCodi.second in 0 until size)
}

fun isNotVisited(
    visited: MutableList<MutableList<Boolean>>,
    firstIndex: Int,
    secondIndex: Int
): Boolean {
    return !visited[firstIndex][secondIndex]
}

fun isHouse(
    matrix: MutableList<MutableList<Int>>,
    firstIndex: Int,
    secondIndex: Int
): Boolean {
    return matrix[firstIndex][secondIndex] == 1
}

fun readMatrix(size: Int): MutableList<MutableList<Int>> {
    val matrix: MutableList<MutableList<Int>> = mutableListOf()
    for (i in 0 until size) {
        matrix.add(
            readLine()!!
                .split(" ")
                .map { it.toInt() }
                .toMutableList()
        )
    }
    return matrix
}

에필로그

  • 진짜 엥간히 바쁘지 않으면 꼭 정답지 공개시한 24시간 내로 문제 풀고 싶었는데, 이번에는 그러지 못했다
  • 처음 한시간에 “대충 다 풀었는데, 숫자가 정확하지 않네 헬스다녀와서 디버깅해야지” 라는 생각으로 접고 시간이 흐른 뒤에 보니
    • 만들다 만 코드가 이렇게 미워보일수 없었다. ㅠㅠ
  • 그런고로.. 이 뭐랄까.. 세상에서 가장 위험한 코드는 역시 “만들다 만 코드” 가 아닐까 싶다.
  • 현업개발에서도 보면 누군가가 “이것만 고치면 됨 ㅎㅎ” 하면서 넘겨받는게 가장 위험하고 거대한 폭탄 이라는 진실처럼..