DFS와 BFS를 활용한 네트워크(연결된 그룹) 개수 구하기

DFS와 BFS를 활용한 네트워크(연결된 그룹) 개수 구하기

1. 연결된 그룹을 세는 기본 개념

암시적으로 표현된 그래프에서도 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 이용해 연결된 덩어리(그룹, 네트워크)의 개수를 셀 수 있다.

• DFS나 BFS를 한 번 실행하면 하나의 네트워크 전체를 방문하게 된다.
• 아직 방문하지 않은 노드를 찾았다면, 새로운 네트워크의 시작점이다.

즉, 네트워크 수를 구한다는 건 그래프를 순회하며 새로운 연결 그룹이 등장할 때마다 count를 하나씩 증가시키는 것과 같다.

2. 네트워크 개수 세는 절차

1. 그래프의 모든 좌표를 순회
2. 특정 조건을 만족하는 노드를 찾음 (예: 값이 1)
3. 해당 노드를 아직 방문하지 않았다면 DFS/BFS 실행
4. 탐색이 끝나면 네트워크 개수 +1
5. 모든 노드를 확인할 때까지 반복

예시 코드

for (int r = 0; r < rowLen; r++) {
    for (int c = 0; c < colLen; c++) {
        if (grid[r][c] == 1 && !visited[r][c]) {
            dfs(r, c); // 또는 bfs(r, c)
            count++;   // 새로운 네트워크 발견
        }
    }
}

 

3. 예시: 2차원 배열로 표현된 그래프

// 암시적 그래프: 1은 노드, 상하좌우로 연결됨
int[][] grid = {
    {1, 1, 0, 0}, 
    {1, 0, 0, 0}, 
    {0, 1, 1, 0}, 
    {0, 0, 1, 1}
};

해당 그래프에서 연결된 그룹은 2개

[네트워크 1]
 (0,0) - (0,1)
    |
 (1,0)

[네트워크 2]
 (2,1) - (2,2)
                 |
             (3,2) - (3,3)

 

4. 네트워크 개수 세기 (Java 코드)

public static int countNetworks(int[][] inputGrid) {
    grid = inputGrid;
    rowLen = grid.length;
    colLen = grid[0].length;
    visited = new boolean[rowLen][colLen];
    int count = 0;

    for (int r = 0; r < rowLen; r++) {
        for (int c = 0; c < colLen; c++) {
            if (grid[r][c] == 1 && !visited[r][c]) {
                dfs(r, c);  // 또는 bfs(r, c)
                count++;    // 연결 그룹 수 증가
            }
        }
    }
    return count;
}