Today's Challenge

fabichoi 2023. 1. 13. 23:45

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

Longest Path With Different Adjacent Characters - LeetCode

Longest Path With Different Adjacent Characters - You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, w

leetcode.com

최장거리 구하기. 일단 잘 모르겠어서 바로 솔루션행 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ =_=;;

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int: 
        tree = defaultdict(list)
        for end, start in enumerate(parent):
            tree[start].append(end)
        
        res = 1

        def dfs(node):
            nonlocal res
            mx1 = mx2 = 0

            for nei in tree[node]:
                neiL = dfs(nei)
                if s[nei] != s[node]:
                    if neiL > mx1:
                        mx2 = mx1
                        mx1 = neiL
                    elif neiL > mx2:
                        mx2 = neiL
            
            res = max(res, mx1+mx2+1)
            return mx1 + 1
        
        dfs(0)
        
        return res