Daily LeetCode Challenge - 2246. Longest Path With Different Adjacent Characters

Problem From.

https://leetcode.com/problems/longest-path-with-different-adjacent-characters/

오늘 문제는 한 노드에서 다른 노드로 이어지는 경로중에서 서로 알파벳이 다른 이웃노드를 가진 가장 긴 경로를 반환하는 문제였다.

제일 처음 접근은 DFS 로 하였다. DFS 를 쓰면 한 노드에서 자식노드로 가는 경로를 끝까지 구할 수 있는데, 한번에 한 경로의 끝까지밖에 볼 수 없으므로, 가장 긴 두가지 경로를 더한 값이 가장 긴 경로가 될 것이다.

시작노드에서부터 DFS 알고리즘을 사용하여 그 전의 노드와 알파벳이 다른 노드를 탐색해나가며, 가장 긴 경로를 max 값으로 비교하여 반환하는 식으로 풀었다.

class Solution {
    
    private var longestPath = 1
    
    fun longestPath(parent: IntArray, s: String): Int {
        
        val n = parent.size
        val children: MutableMap<Int?, MutableList<Int>> = HashMap()
        for (i in 1 until n) {
            children.computeIfAbsent(
                parent[i]
            ) { value: Int? -> ArrayList() }.add(i)
        }
        dfs(0, children, s)
        return longestPath
        
    }
    
    fun dfs(currentNode: Int, children: Map<Int?, MutableList<Int>>, s: String): Int {
        if (!children.containsKey(currentNode)) {
            return 1
        }

        var longestChain = 0
        var secondLongestChain = 0
        for (child in children[currentNode]!!) {
            val longestChainStartingFromChild = dfs(child, children, s)
            if (s[currentNode] == s[child]) {
                continue
            }
            if (longestChainStartingFromChild > longestChain) {
                secondLongestChain = longestChain
                longestChain = longestChainStartingFromChild
            } else if (longestChainStartingFromChild > secondLongestChain) {
                secondLongestChain = longestChainStartingFromChild
            }
        }

        longestPath = Math.max(longestPath, longestChain + secondLongestChain + 1)
        return longestChain + 1
    }
    
}

DFS 의 마지막 +1 은 시작노드를 포함하여야 하기 때문에 +1 을 해주었다.
위 풀이의 시간복잡도는 O(n) 이 된다.