[BJ] 11724 - 연결 요소의 개수

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 백준 11724번 연결 요소의 개수에 대해 포스팅하겠습니다.

 

 

 

연결 요소(connected component)

세 개의 연결 요소

In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

연결 요소란, 무향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프를 의미한다고 하네요. 앞부분은 그렇다 쳐도 뒷부분은 뭔말인지 저도 이해가 안갑니다..

어찌됬건, 위 사진과 같이 서로 연결된 하나의 덩어리를 연결 요소라고 생각하면 편합니다.

 

 

접근 방법

처음에는 ratsgo님의 포스팅을 참고해서 집합을 이용하여 풀려고 했으나, 무수한 중첩반복의 요청때문에 포기했습니다...

구글링을 좀 해보니, DFS로 풀 수 있다고 했습니다만, 사실 잘 이해가 안갔습니다.

몇시간동안 코드 동작을 그려보면서 이해하니, 로직이 이해가 갔습니다. 

 

해당 문제를 푸는데 중요하다고 생각한 요소들은 다음과 같습니다.

• DFS : 방문 가능한 모든 정점을 방문합니다. 방문한 정점과 연결된 다른 정점도 방문합니다.
• visited : 이미 방문한 정점을 다시 방문하는 것과 무한 루프에 빠지는 것을 방지하기 위한 정보입니다.
• 인접행렬 or 인접배열 : 정점 간 연결 관계를 포현하기 위한 자료구조입니다.

 

해당 문제의 큰 로직은

1. 그래프의 특정 정점 a에 방문합니다. 그리고 a와 연결된 정점 b를 방문합니다. 또 b와 연결된 정점 c를 방문합니다.
2. 1번 과정을 반복하여 a와 연결된 모든 정점을 방문한 후, 카운트를 1 증가시킵니다.
3. 1~2의 과정을 모든 정점에 대해 반복하여, 최종 카운트 값이 연결 요소의 개수가 됩니다.

여기서 무향 그래프이므로, 하나의 엣지로 연결된 두 정점(a, b)에 대해, a -> b로 방문하는 경우와 b -> a로 방문하는 경우는 동일합니다. 또한 a와 연결된 모든 정점을 방문 후 b와 연결된 정점을 방문하려고 할 때, a를 방문하는 과정에서 b는 이미 방문했으므로 다시 방문할 필요가 없습니다. 이러한 경우를 방지하기 위해 visited라는 배열을 선언하여, 각 정점별로 방문 여부를 표시합니다.

 

인접 행렬

인접 배열

정점 간 연결 여부를 표현하기 위해서는 인접행렬 혹은 인접배열을 이용할 수 있습니다.

두 자료구조의 차이점에 대해서는 하단 참고 목록의 공대사랑님의 포스팅을 참고해주세요.

 

 

풀이 코드 (java)

인접 행렬을 이용한 코드입니다.

import java.util.Scanner;

public class Main {
    private static int[] visit;
    private static int[][] graph;
    
    private static void DFS(int x, int N, int cnt) {
        visit[x] = cnt;
        for (int i = 0; i < N; i++) {
            if (graph[x][i] == 1 && visit[i] == 0) {
                DFS(i, N, cnt);
            }
        }
    }
    
    public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        graph = new int[N][N];
        visit = new int[N];

        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x - 1][y - 1] = graph[y - 1][x - 1] = 1;
        }
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (visit[i] == 0) {
                cnt++;
                DFS(i, N, cnt);
            }
        }
        System.out.println(cnt);        
    }
}

 

인접 배열을 이용한 코드입니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private static int[] visit;
    private static ArrayList<ArrayList<Integer>> list;
    
    private static void DFS(int v, int N, int cnt) {
        if(visit[v] == 0) {
            visit[v] = cnt;

            list.get(v).forEach(vertex -> {
                DFS(vertex, N, cnt);
            });
        }
    }
    
    public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        list = new ArrayList<>(N);
        for(int i = 0; i < N; i++) list.add(new ArrayList<>());
        visit = new int[N];

        for (int i = 0; i < M; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            list.get(x-1).add(y - 1);
            list.get(y-1).add(x - 1);
        }
        final int[] cnt = {0};
        final int[] i = {0};
        list.forEach(arrayList -> {
            if(visit[i[0]] == 0) {
                cnt[0]++;
                DFS(i[0], N, cnt[0]);
            }
            i[0]++;
        });
        System.out.println(cnt[0]);
    }
}

 

 

참고

영문위키의 연결 요쇼

letsgo님의 연결 요소 포스팅

공대사람님의 인접 행렬과 인접 리스트 포스팅