Graphs

1971. Find if Path Exists in Graph

n개의 정점이 있는 양방향 그래프가 있는데, 각 정점에는 0부터 n-1까지(포함)의 레이블이 지정되어 있습니다. 그래프의 모서리는 2차원 정수 배열 edges로 표현되며, 각 edges[i] = [ui, vi]는 정점 ui와 정점 vi ​​사이의 양방향 모서리를 나타냅니다. 각 정점 쌍은 최대 하나의 모서리로 연결되며, 어떤 정점도 자기 자신에게 모서리를 갖지 않습니다. 정점 소스에서 정점 목적지까지 유효한 경로가 있는지 확인하고 싶습니다. 주어진 모서리와 정수 n, 소스, 목적지에 대해 소스에서 목적지까지 유효한 경로가 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

 

제약사항

• 1 <= n <= 2 * 10^5
• 0 <= edges.length <= 2 * 10^5
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= source, destination <= n - 1
• 중복된 edges는 없습니다.
• self edges 없습니다.

아이디어

1. 그래프 만들기

2. dfs로 돌면서 목적지와 동일한지 확인

class Solution {
    private boolean dfs(List<List<Integer>> graph, boolean[] visited, int current, int destination) {
        if (current == destination) return true;
        visited[current] = true;

        for (int neighbor : graph.get(current)) {
            if (!visited[neighbor]) {
                if (dfs(graph, visited, neighbor, destination)) {
                    return true;
                }
            }
        }

        return false;
    }
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        boolean[] visited = new boolean[n];

        return dfs(graph, visited, source, destination);
    }
}

---

695. Max Area of Island

m x n 이진 행렬 격자가 주어집니다. 섬은 육지를 나타내는 1들이 네 방향(수평 또는 수직)으로 연결된 집합입니다. 격자의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다. 섬의 면적은 섬에서 값이 1인 셀의 개수입니다. 격자에서 섬의 ​​최대 면적을 반환합니다. 섬이 없으면 0을 반환합니다.

 

제약사항

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j]는 0 or 1

아이디어

1. for문 돌면서 1이면 dfs를 통해 면적 구하기

2. 면적 최댓값 갱신

class Solution {

    private int dfs(int[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
            return 0;
        }

        grid[r][c] = 0;

        int area = 1;
        area += dfs(grid, r - 1, c);
        area += dfs(grid, r + 1, c);
        area += dfs(grid, r, c - 1);
        area += dfs(grid, r, c + 1);

        return area;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        int rows = grid.length;
        int cols = grid[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int area = dfs(grid, r, c);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }
}

---

2368. Reachable Nodes With Restrictions

0에서 n-1까지 레이블이 지정된 n개의 노드와 n-1개의 간선을 갖는 무방향 트리가 있습니다. 길이가 n - 1인 2차원 정수 배열 edges가 주어집니다. 여기서 edges[i] = [ai, bi]는 트리의 노드 ai와 bi 사이에 간선이 있음을 나타냅니다. 또한 제한된 노드를 나타내는 정수 배열 restricted가 주어집니다. 제한된 노드를 방문하지 않고 노드 0에서 도달할 수 있는 최대 노드 수를 반환합니다.

노드 0은 제한된 노드가 아닙니다.

 

제약사항

• 2 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges represents a valid tree.
• 1 <= restricted.length < n
• 1 <= restricted[i] < n
• All the values of restricted are unique.

아이디어

1. 그래프 만들고

2. 0에서 출발해서 노드 카운트

   - 제한된 노드 빼고

class Solution {
    private int dfs(int node, List<List<Integer>> graph, Set<Integer> restrictedSet, boolean[] visited) {
        if (restrictedSet.contains(node) || visited[node]) return 0;

        visited[node] = true;
        int count = 1;

        for (int neighbor : graph.get(node)) {
            count += dfs(neighbor, graph, restrictedSet, visited);
        }

        return count;
    }
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        Set<Integer> restrictedSet = new HashSet<>();
        for (int r : restricted) {
            restrictedSet.add(r);
        }

        boolean[] visited = new boolean[n];
        return dfs(0, graph, restrictedSet, visited);
    }
}