2023.11.11 Today's Challenge

https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/

Restore the Array From Adjacent Pairs - LeetCode

DFS로 푸는 문제.
인접 리스트를 만들어서 풀면 될 것 같다는 생각이 어렴풋이 들긴 했는데 결국 못품 ㅠㅠ
그래도 로컬에서 디버깅 하면서 어떤 개념으로 돌아가는지 눈으로 한번 더 확인함.
사실 모르면 안되는 부분일 수 있긴한데.. 뭐 다음에는 해설 안보고 인접 리스트까지 만드는 것만 해도 충분 할 듯

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        gr = defaultdict(list)

        for x, y in adjacentPairs:
            gr[x].append(y)
            gr[y].append(x)
                    
        root = None 
        for n in gr:
            if len(gr[n]) == 1:
                root = n
                break
            
        def dfs(node, prev, ans):
            ans.append(node)
            for nei in gr[node]:
                if nei != prev:
                    dfs(nei, node, ans)
            
        ans = []
        dfs(root, None, ans)
        return ans