.leetcode(261. Graph Valid Tree)

https://leetcode.com/problems/graph-valid-tree/

 

1. 2022/04/12 시도

소요시간: 37분

class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] root = new int[n];
        for (int i=0; i<n; i++) {
            root[i] = i;
        }
        for (int i=0; i<edges.length; i++) {
            int p = edges[i][0];
            int c = edges[i][1];
            
            if (root[c] == c) {
                root[c] = p;
            } else if (root[p] == p) {
                root[p] = c;
            } else {
                return false;
            }
        }
        
        int p = find(root, 0, n, 0);
        for (int i=1; i<n; i++) {
            int r = find(root, i, n, 0);
            if (r == -1) {
                return false;
            }
            if (p != r) {
                return false;
            }
        }
        
        return true;
    }
    
    private int find(int[] root, int index, int n, int counter) {
        if (n < counter || index == -1) {
            return -1;
        }

        if (index == root[index]) {
            return index;
        }
        
        return root[index] = find(root, root[index], n, counter+1);
    }
}

풀이 접근 과정

부모를 한쪽으로 결정하고 이미 부모가 있는 경우는 자식노드로 본다.
그런데 만약에 부모도 자식도 아닌 경우는 유효한 트리가 아닌 것으로 판단한다.

또한 루트가 2개인 경우도 트리가 유효하지 않다고 판단한다.

 

느낀점

• 이게 그래프 문제인데 조금 어설프게 풀었다.
• 솔루션을 공부했을 때, 다양한 풀이를 경험할 수 있었다.
• 그중에서 위에 내가 구현하고자 하는 부모/자식 관계 알고리즘에 대해서 소개한다.

class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i=0; i<n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        for (int[] edge: edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }
        
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        Map<Integer, Integer> parent = new HashMap<>();
        parent.put(0, -1);
        while(!stack.isEmpty()) {
            int node = stack.pop();
            for (int nbh : adjacencyList.get(node)) {
                if (parent.get(node) == nbh) {
                    continue;
                }
                if (parent.containsKey(nbh)) {
                    return false;
                } 
                
                stack.push(nbh);
                parent.put(nbh, node);
            }
        }

        return parent.size() == n;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형