802. Find Eventual Safe States (JAVA)

출처 : https://leetcode.com/problems/find-eventual-safe-states/description/?envType=daily-question&envId=2025-01-24

문제

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

 

n개의 노드로 이루어진 방향 그래프가 있으며, 각 노드는 0부터 n-1까지 라벨링되어 있습니다. 이 그래프는 0-인덱스 기반 2D 정수 배열 graph로 표현됩니다. 여기서 graph[i]는 노드 i와 인접한 노드들의 정수 배열을 나타내며, 이는 노드 i에서 graph[i]에 있는 각 노드로 향하는 간선이 있음을 의미합니다.

노드 i가 터미널 노드(terminal node)라면, i에서 나가는 간선이 없습니다.
노드 i가 안전 노드(safe node)라면, 해당 노드에서 시작하는 모든 경로가 터미널 노드 또는 다른 안전 노드로 이어집니다.

이 그래프에서 모든 안전 노드를 포함하는 배열을 반환하세요. 반환되는 배열은 오름차순으로 정렬되어 있어야 합니다.

 

 

접근 : DFS

 

1. 노드 i가 터미널 노드(terminal node)라면, i에서 나가는 간선이 없습니다.
2. 노드 i가 안전 노드(safe node)라면, 해당 노드에서 시작하는 모든 경로가 터미널 노드  또는 다른 안전 노드로 이어집니다.

 

결국 해당 노드가 안전노드라면 해당노드에서 시작하는 모든 경로가 결국 터미널 노드로 이어져야함. 안전 노드가아니라면 동일한 구간을 반복하는 싸이클을 형성하게된다는점을 알수있음.

 

dfs탐색을통해 해당노드로부터 발생하는 경로중 싸이클이 발생한다면 안전노드에서 제외하는 방식으로 문제를 해결가능.

public class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        boolean[] visited = new boolean[graph.length];
        boolean[] isSafe = new boolean[graph.length];
        int n = graph.length;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            out[i] = graph[i].length;
        }
        for (int i = 0; i < n; i++) {
            dfs(graph,i,out,isSafe,visited);
        }
        for (int i = 0; i < n; i++) {
            if(isSafe[i]){
                res.add(i);
            }
        }
        return res;
    }
    public boolean dfs(int[][] graph, int cur, int[] out, boolean[] isSafe,boolean[] vis){
        if(vis[cur]){//이미 방문한 노드라면 해당 노드의 안전여부반환
            return isSafe[cur];
        }
        if(out[cur] == 0 || isSafe[cur]){//해당노드가 터미노드 or 안전노드라면 true반환
            return isSafe[cur]=true;
        }
        //방문처리
        vis[cur] = true;
        boolean safe = true;
        for(int k = 0; k < graph[cur].length; k++){
        //모든 경로중 하나라도 안전노드가 아니라면 safe는 false가 된다.
            safe &= dfs(graph,graph[cur][k],out,isSafe,vis);
        }

        return isSafe[cur] = safe;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.eventualSafeNodes(new int[][]{{1,2},{2,3},{5},{0},{5},{},{}});
    }
}