[BOJ] 11724 연결요소의 개수 - JAVA

1. 문제

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

---

2. 풀이

인접리스트 DFS, BFS

인접행렬 DFS, BFS 둘 다 작성하려고 한다.

2-1. 인접리스트

2-1-1. Node 클래스

• 인접리스트로 풀거라 클래스를 만들었다.

private static class Node{
   int data;
   Node link;
   private Node(int data, Node link){
      this.data = data;
      this.link = link;
   }
}

2-1-2. 입력

• 무방향이라 양 쪽 모두 연결처리했다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

head = new Node[N+1];

for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   int u = Integer.parseInt(st.nextToken());
   int v = Integer.parseInt(st.nextToken());

   head[u] = new Node(v,head[u]);
   head[v] = new Node(u,head[v]);
}

 

2-1-3. DFS

• 방문한 적 없는 노드만 dfs 탐색한다. 탐색이 끝난 뒤 count+1한다.

/* main부분 */
int count = 0;
visited = new boolean[N+1];
for(int i=1;i<=N;i++){
   if(visited[i]) continue;
   dfs(i);
   count ++;
}

System.out.println(count);

• for문으로 간단하게 다음 노드로 이동한다. node끼리 링크로 연결되어있으므로 node = node.link로 바꾼다.
• 방문한 적 없다면 방문처리와 함께 그 데이터 dfs탐색을 하고 돌아온다.

private static void dfs(int data) {
   for(Node node = head[data];node!=null;node = node.link){
      if(visited[node.data]) continue;
      visited[node.data] = true;
      dfs(node.data);
   }
}

 

2-1-3. BFS

• 방문한 적 없는 노드일때만 queue에 넣고 카운트+1하는 것은 동일하다.
• 큐가 빌 때까지 큐에서 노드를 꺼내고 꺼낸 노드와 연결된 노드를 다시 큐에 넣는다.
• 큐에 넣을 때 방문처리한다.

/* main 아래부분 */
int count = 0;
boolean[] visited = new boolean[N+1];
Queue<Integer> queue = new ArrayDeque<>();
for(int i=1;i<=N;i++){
   if(visited[i]) continue;
   queue.offer(i);
   count++;

   while(!queue.isEmpty()){
      for(Node node = head[queue.poll()]; node!=null; node = node.link){
         if(visited[node.data]) continue;
         visited[node.data] = true;
         queue.offer(node.data);
      }
   }
}

System.out.println(count);

 

2-2. 인접행렬

2-2-1.입력

• 노드 번호가 1부터 시작해서 [N+1][N+1]칸 배열을 만들었다.
• 무방향이라 [u][v], [v][u] 양쪽에 1을 저장한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

int[][] adjMatrix = new int[N + 1][N + 1];

for (int i = 0; i < M; i++) {
   st = new StringTokenizer(in.readLine());
   int u = Integer.parseInt(st.nextToken());
   int v = Integer.parseInt(st.nextToken());

   adjMatrix[u][v] = 1;
   adjMatrix[v][u] = 1;
}

 

2-2-2. DFS

•  방문한 적 없는 노드만 dfs 탐색한다. 탐색이 끝난 뒤 count+1한다.

/* main부분 */
visited = new boolean[N+1];
int count = 0;
for(int i=1;i<=N;i++) {
   if (visited[i]) continue;
   visited[i] = true;
   dfs(i);
   count++;
}

System.out.println(count);

• 1부터 N까지 이동하면서 지금 노드와 연결되어있다면(adjMatrix[num][i]==1) 방문처리하고 dfs탐색한다.

private static void dfs(int num) {
   for(int i=1;i<=N;i++){
      if(visited[i] || adjMatrix[num][i] != 1) continue;
      visited[i] = true;
      dfs(i);
   }
}

 

2-2-3. BFS

• 방문한 적 없는 노드일때만 queue에 넣고 카운트+1하는 것은 동일하다.
• 큐가 빌 때까지 큐에서 노드를 꺼내고 꺼낸 노드와 연결된 노드를 다시 큐에 넣는다.
• 큐에 넣을 때 방문처리한다.

Queue<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[N + 1];
int count = 0;

for (int i = 1; i <= N; i++) {
   if (visited[i]) continue;
   queue.offer(i);
   visited[i] = true;
   count++;

   while (!queue.isEmpty()) {
      int num = queue.poll();
      for (int j = 1; j <= N; j++) {
         if (visited[j] || adjMatrix[num][j] != 1) continue;
         queue.offer(j);
         visited[j] = true;
      }
   }
}

System.out.println(count);

---

3. 결과

3-1. 인접리스트

아래가 DFS, 위가 BFS

3-2. 인접행렬

아래가 BFS, 위가 DFS

인접행렬은 예상한대로 BFS가 더 빠른데 인접리스트는 DFS가 훨씬 빠르다. 왜인지는 모르겠다.. 알게되면 수정해서 작성하겠다.