[코테연습] 2192. All Ancestors of a Node in a Directed Acyclic Graph

 

- 그래프 문제

 

https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/solutions/5384951/easy-java-python3-c-solution-63-ms/?envType=daily-question&envId=2024-06-29

 

- 문제 분석

 1. 2차원 배열 int[][] edges 는 [from, to] 로 이루어져있다.

 2. 이때, 연결되는 Node 의 순서를 List<List<Integer>> 로 변경해서 나타내라.

 

- 문제 풀이

1. List<List<Integer>> graph 를 선언하여, 연결되는 노드 n 의 수만큼 ArrayList<>() 로 초기화한다.

2.  edges 2차원 배열 from, to 를 graph 에 넣는다.

  2-1. 연결되는 Node 의 수신하는 쪽을 담아야하므로, edges[i][0] 를 add 하고, edges[i][1] 을 get 으로 탐색한다.

3. map 으로 수신하는 Node 의 번호를 저장한다.

  3-1. Map<Integer, Set<Integer>> 로 저장하는 이유는, 수신받는 Node 가 연결된다면 연결되는 Node 를 모두 graph 에 저장해야 하기 때문이다.

4. 3 중 반복문으로 graph 를 탐색하고, map 에 수신받는 Node 가 있으면, graph 에 추가로 연결한다.

  4-1. 중복을 피하기 위해서 contains 함수를 사용한다.

  4-2. Collections sort 함수로 정렬한다.

 

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i = 0; i < edges.length; i++) {
            int front = edges[i][0];
            int back = edges[i][1];
            graph.get(back).add(front);
            Set<Integer> set = new HashSet<>();
            if (map.get(back) != null) {
                set = map.get(back);
            }
            set.add(front);
            map.put(back, set);
        }

        for(int i = 0; i < graph.size(); i++) {
            List<Integer> list = graph.get(i);
            for(int j = 0; j < list.size(); j++) {
                int ele = list.get(j);
                if (map.get(ele) != null) {
                    Set<Integer> set = map.get(ele);
                    for(int num : set) {
                        if (!graph.get(i).contains(num)) graph.get(i).add(num);
                    }
                }
            }
            Collections.sort(graph.get(i));
        }
     
        return graph;
    }
}

 

 

 

------ 

 

graph 에 숫자를 모두 담은 후에 백트래킹으로 푸는 방법도 있어서 가지고 온다.

 

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
    List<List<Integer>> ans = new ArrayList();
    List<List<Integer>> dc = new ArrayList();
    for (int i = 0; i < n; i++) {
        ans.add(new ArrayList());
        dc.add(new ArrayList());
    }
    for (int[] e: edges) 
        dc.get(e[0]).add(e[1]);
    for (int i = 0; i < n; i++) 
        dfs(i, i, ans, dc);
    return ans;
}
private void dfs(int x, int curr, List<List<Integer>> ans, List<List<Integer>> dc) {
    for (int ch: dc.get(curr))
        if(ans.get(ch).size() == 0 || ans.get(ch).get(ans.get(ch).size() - 1) != x) {
            ans.get(ch).add(x);
            dfs(x, ch, ans, dc);
        }
}
}