[백준 : 1926] 그림 (kotlin)

JJAE WON·2022년 10월 8일

알고리즘

👇🏻 문제 확인하기
백준 : 1926 - 그림

문제

입출력

문제풀이

전형적인 DFS/BFS 문제이기 때문에 문제를 설계하는 건 금방했다.

도화지를 돌면서 1을 만날 경우 bfs탐색을 해준다.
bfs함수를 호출하는 횟수가 그림의 개수이다.
bfs함수는 1의 갯수를 반환값으로 주는데 그 반환값들이 그림의 넓이이다.
3번에서 반환되어진 값들 중 가장 큰 값이 가장 넓은 그림의 넓이이다.

설계를 금방했고 코드도 금방짜서 백준에 제출했는데...
메모리초과 로 문제를 계속 틀렸다....

1️⃣ 메모리 초과 원인 찾기

val graph : MutableList<MutableList<Int>> = mutableListOf()

fun main(){
    val (n,m) = readln().split(" ").map { it.toInt() }
    var count = 0
    repeat(n){
        val list = readln().split(" ").map { it.toInt() }.toMutableList()
        graph.add(list)
    }
}

알고리즘 문제 풀 때 아무 생각 없이 mutableList 를 썼는데 이것이 문제였다.
mutableList를 List 인터페이스를 캐스팅하여 사용하고 있는데 그렇다면 List 자료구조의 특징을 생각해 봐야 했다. 짧게 나마 정리하자면

List 특징

순서가 있는 자료형
불연속적인 메모리 공간을 점유한다.
동적 타입이기 때문에 자유자재로 늘어났다 줄어든다.
메모리의 재사용이 용이하다.
삽입 삭제 동작이 빠르다.
포인터를 통해 다음 값을 가르키므로 포인터를 담기 위한 추가적인 메모리 공간이 필요하다.

2번의 불연속적인 메모리 공간을 가지고 있다는 특징때문에 생길 수 있는 장점이 메모리 관리에 용이한 점이 있고 단점으로는 검색 성능이 좋지 않다는 점이 있다.

알고리즘 문제를 풀 때, 만약 삽입삭제가 자주 일어나야 하는 변수라면 list를 사용하는 것이 좋겠지만 size가 정해져있고 더 이상 size가 변하지 않는 변수라면 굳이... List를 사용할 필요가 없다.

그래서 메모리 공간을 정해놓고 쓸 수 있는 정적타입인 Array 로 바꿔서 변수를 선언해 주었다.
추가적으로 (1)반복적으로 할당되는 변수들을 전역변수로 빼주었고, (2) 변수선언이 필요없는 것들을 최대한 제거해주었다.

lateinit var canvas : Array<IntArray>

fun main(){
    var num = 0
    var area = 0
    val (n,m) = readln().split(" ").map{ it.toInt()}
    canvas = Array(n){ IntArray(m) } // array 크기 지정
    repeat(n){i ->
        val list = readln().split(" ").map { it.toInt()}
        list.forEachIndexed { j, n ->
            canvas[i][j] = n
        }
    }

2️⃣ 시간초과 원인 찾기

알고리즘 한 문제 푸는데 메모리초과에 시간초과도 나는 사람은 나밖에 없을 것이다..
그만큼 생각이 없다는 것을 의미하는 듯🥲
메모리초과 문제를 해결했더니 시간초과가 났다..ㅎㅎ (절망적)

코드에서 시간을 줄일 수 있는 부분이 어디일까 생각해봤다.
bfs 함수에서는 줄일 수 있는 곳이 없다고 생각했다.... 그러던 중 든 생각!

    canvas.forEachIndexed canvasLoop@{ x, list ->
        list.forEachIndexed { y, nn ->
            if (canvas.count{ it.all { it == 0 } } == n){
                return@canvasLoop
            }
            if(canvas[x][y] == 1){
                area = max(area, bfs(x,y))
                num++
            }
        }
    }

🧐 for 문과 forEach 중 무엇이 빠를까...

찾아본 결과.. for문과 forEach문은 서로서로 바꿀 수 있는데
단순한 반복문일 경우 for문이 더 빠르다!!!!!!!!!!!!!!!

왜냐하면, forEach 문은 람다형식 으로 호출되기 때문에 당연히 퍼포먼스가 저하될 수 밖에 없다고 한다. 하지만! Kotlin의 컬렉션인 List,Map,Set와 함께 사용될 땐 for문보다 우수한 퍼포먼스가 생긴다.

    for (i in 0 until n) for(j in 0 until m){
        if(canvas[i][j] == 1){
            area = max(area, bfs(i,j))
            num++
        }
    }

Array를 반복해야 할 땐 for문으로도 충분하다...

전체 코드(kotlin)

lateinit var canvas : Array<IntArray>
val dx = intArrayOf(0,1,0,-1)
val dy = intArrayOf(1,0,-1,0)

fun main(){
    var num = 0
    var area = 0
    val (n,m) = readln().split(" ").map{ it.toInt()}
    canvas = Array(n){ IntArray(m) }
    repeat(n){i ->
        val list = readln().split(" ").map { it.toInt()}.toMutableList()
        list.forEachIndexed { j, n ->
            canvas[i][j] = n
        }
    }

    fun bfs(x: Int, y : Int) : Int {
        var count = 1
        val queue = mutableListOf<Pair<Int,Int>>()
        queue.add(Pair(x,y))
        canvas[x][y] = 0

        while (queue.isNotEmpty()){
            repeat(queue.size){
                val front = queue.removeLast()
                repeat(4){time ->
                    val nx = front.first+dx[time]
                    val ny = front.second+dy[time]
                    if(nx in canvas.indices && ny in 0 until canvas[nx].size ){
                        if(canvas[nx][ny] == 1){
                            canvas[nx][ny] = 0
                            queue.add(Pair(nx,ny))
                            count++
                        }
                    }

                }
            }
        }
        return count
    }

    for (i in 0 until n) for(j in 0 until m){
        if(canvas[i][j] == 1){
            area = max(area, bfs(i,j))
            num++
        }
    }

    println(num)
    println(area)
}