[백준 11724] 연결 요소의 개수 (JAVA)

백준 11724번 문제  - 연결 요소의 개수

11724번: 연결 요소의 개수

---

문제 분석

 

 

• 입력된 간선들을 토대로 정점들의 연결을 알아내, 연결 요소의 개수를 알아내 출력

---

해결 키 포인트

 

• DFS(깊이 우선 탐색) 개념 파악
• 연결 요소 개념 파악
  • 연결 요소: 각 노드들이 뭉쳐진 묶음 개수
• 간선을 입력받아서 각 정점에 존재하는 연결 노드를 알아내야 한다.
  • 해당 정보를 가지고, 후에 연결 요소 개수를 알 수 있다.
• 모든 정점을 확인했는지 판단하기 위해 배열을 제작해야 함
  • 추가적으로 boolean 변수를 제작하면 반복문을 끝내는데 도움을 준다.

 

---

깊이 우선 탐색(DFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

기능, 특징, 시간 복잡도

 

• 기능 : 그래프 완전 탐색
• 특징
  • 재귀 함수로 구현
  • 스택 자료 구조 이용
• 시간 복잡도 (노드 수: V, 에지 수: E)
  • O(V+E)

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

 

깊이 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입 선출 특성을 가짐 ( 재귀함수 사용 많음 / 스택도 사용 )

 

알고리즘

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 (이를 모든 정점을 다한다)

 

Do It! 알고리즘 코딩 테스트

 

만약 스택에 노드가 없으면, 방문하지 않은 정점을 알아내, 스택에 삽입하고 다시 2번 단계를 반복한다.

---

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N, M 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 각 인접 리스트 저장할 큐 및 값을 확인했는지 체크하는 isCheck 초기화
        Queue<Integer> [] queues = new Queue[N];
        boolean [] isCheck = new boolean[N];

        for(int i=0;i<N;i++) {
            queues[i] = new LinkedList<>();
            isCheck[i] = false;
        }

        // 수 입력
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            queues[u-1].add(v-1);
            queues[v-1].add(u-1);
        }

        // DFS를 실행을 도와줄 queue
        Queue<Integer> result = new LinkedList<>();

        // 확인할 index i, 연결요소 개수 count
        int i;
        int count = 0;

        // 지금 모든 수를 확인했는지 결과
        boolean isClear = false;

        // 모든 수를 확인하기 전까지 반복
        while(!isClear) {
            // 지금 result 큐에 수가 있을 경우
            if (!result.isEmpty()) {
                // 큐에서 꺼내 i로 등록
                i = result.poll();
            // 지금 result 큐에 수가 없을 경우
            } else {
                // index 초기화하고 지금 확인하지 않은 수를 찾아 i로 등록
                i = 0;
                // queue에 아무것도 없을 시 연결 리스트가 더이상 없는 것, 즉 연결이 끝난것이므로 연결 요소 개수 증가
                count++;
                while (isCheck[i]) {
                    i++;
                    // 마지막 index 다음까지 확인하지 않은 수가 없을 경우, isClear를 true로 해서 while 종료
                    if (i == N) {
                        isClear = true;
                        break;
                    }
                }
            }
            // 모든 수를 확인하지 않았을 경우
            if (!isClear) {
                // 해당 index를 확인한 수로 변환
                isCheck[i] = true;
                int preIndex = i;
                // 해당 인덱스와 연결된 인접 리스트 다 확인하여 result 큐에 추가
                while (!queues[preIndex].isEmpty()) {
                    i = queues[preIndex].poll();
                    if (!isCheck[i]) {
                        result.add(i);
                        isCheck[i] = true;
                    }
                }
            }
        }

        // 출력
        System.out.println(count-1);
    }
}