DFS를 Recursion으로 구현할 때 팁

1. adjMatrix -> adjList

Node의 수가 많은 경우, adjMatrix로 그래프 정보를 저장하면 메모리 초과(OOM) 예외가 발생한다. 그러므로 adjList로 대신하자.

2. Recursion -> Stack

OOM과는 별개로, Recursion Depth가 너무 깊어지면, StackOverflowError (프로그래머스에서는 런타임 에러라고만 뜬다)가 발생한다.
그럴 땐 Recursion이 아닌, Stack으로 구현하도록 한다.

프로그래머스 - 모두 0으로 만들기

여기서 SO가 뜨기에 Stack으로 대체했다.

Recursion Ver.

	fun mySolution(a: IntArray, edges: Array<IntArray>): Long {
            weight = a.map{it.toLong()}.toMutableList()
            adj = MutableList(a.size) { mutableListOf<Int>() }
            for (e in edges) {
                adj[e[0]].add(e[1])
                adj[e[1]].add(e[0])
            }
            if (a.all { it == 0 }) return 0
            else if (a.sum() != 0) return -1

            val (res, count) = dfs(0, 0)
            return count

        fun dfs(curNode: Int, parent: Int): Pair<Long, Long> {
            var res = weight[curNode].toLong()
            var count = 0L
            for (i in adj[curNode]) {
                if (i != parent) {
                    val pair = dfs(i, curNode)
                    res += pair.first
                    count += pair.second
                    count += abs(pair.first)
                }
            }
            println("$curNode return Pair: ${Pair(res, count)}")
            return Pair(res, count)
        }

Stack Ver.

        fun solution(a: IntArray, edges: Array<IntArray>): Long {
            weight = a.map{it.toLong()}.toMutableList()
            adj = MutableList(a.size) { mutableListOf<Int>() }
            for (e in edges) {
                adj[e[0]].add(e[1])
                adj[e[1]].add(e[0])
            }
            if (a.all { it == 0 }) return 0
            else if (a.sum() != 0) return -1

            val visited = BooleanArray(a.size)
            var count = 0L
            val stack = Stack<Node>()
            stack.push(Node(0, 0))
            while (stack.isNotEmpty()) {
                val (curNode, parent) = stack.pop()

                if (visited[curNode]) {
                    count += abs(weight[curNode])
                    weight[parent] += weight[curNode]
                    weight[curNode] = 0
                    continue
                }

                visited[curNode] = true
                stack.push(Node(curNode, parent))

                for (i in adj[curNode]) {
                    if (!visited[i]) stack.push(Node(i, curNode))
                }
            }
            return count
        }

3. 자료형

이건 모든 경우에 해당하는 경우지만, Int로 선언한 변수에 그보다 큰 데이터를 넣으면 오버플로우가 나서 값이 달라진다. 그러므로 항상 유의하자.