연결된 영역 개수 찾는 유형

DFS & BFS를 활용한 네트워크 개수 찾기

1. 네트워크란?

네트워크는 서로 연결된 노드들의 집합
노드 A에서 B로 직접 또는 간접적으로 도달할 수 있다면 같은 네트워크로 간주한다.
연결이 전혀 없는 노드는 단독 네트워크로 취급된다.

결국 네트워크 개수를 구한다는 것은 연결된 그룹의 수를 세는 것!

2. DFS와 BFS의 공통점

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 모두 그래프 탐색 알고리즘이다.

• 특정 노드에서 출발해 연결된 모든 노드를 방문한다.
• 한 번의 DFS/BFS 실행으로 하나의 네트워크 전체를 탐색할 수 있다.

이 특징을 이용하면 방문하지 않은 노드에서 DFS/BFS를 시작할 때마다 새로운 네트워크를 찾을 수 있다.

3. 네트워크 개수 구하는 로직

핵심 아이디어

• DFS/BFS 한 번 실행 = 하나의 네트워크 전체 탐색
• 방문하지 않은 노드 발견 = 새로운 네트워크 발견

알고리즘 흐름

1. 모든 노드 순회
2. 방문하지 않은 노드를 발견하면 DFS 또는 BFS 실행
3. 탐색이 끝나면 네트워크 개수 1 증가
4. 모든 노드를 확인할 때까지 반복

4. 코드 구현 예시 (Java)

그래프 정의

Map<Integer, List<Integer>> graph = new HashMap<>() {{
    put(0, List.of(1, 3));
    put(1, List.of(0, 3, 5));
    put(2, List.of(4));
    put(3, List.of(0, 1));
    put(4, List.of(2));
    put(5, List.of(1));
}};

이 그래프는 두 개의 네트워크로 나뉜다.

• 네트워크 1: 0 - 1 - 3 - 5
• 네트워크 2: 2 - 4

네트워크  계산 함수

public int countNetworks(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    int count = 0;

    for (int cur : graph.keySet()) {
        if (!visited.contains(cur)) {
            dfs(graph, cur, visited);
            count++;
        }
    }

    return count;
}

DFS 함수 예시

public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    for (int neighbor : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}