공부 183일차: 백준 11724번 연결 요소의 개수 자바 java

11724 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

 

 

---

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

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	87163	39691	26182	42.546%

문제

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

제한

 

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

힌트

 

 

 

 

---

과정 생각해보기

---

 

연결 요소가 무엇인지만 파악한다면 어렵지 않은 문제다

 

6 5
1 2
2 5
5 1
3 4
4 6

예제 1에서는 이렇게 두 그래프가 만들어진다

따라서, DFS를 끝까지 수행하면 그래프 1개가 완성되는 것이므로 이 개수를 세면 된다이때, depth는 그래프마다 다르기 때문에 굳이 메서드의 매개변수로 넣어줄 필요 없다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m, component;
    static boolean[] visited;
    static ArrayList<Integer>[] list;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(st.nextToken());    // 정점(노드) 개수
        list = new ArrayList[n];
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        m = Integer.parseInt(st.nextToken());    // 간선 개수
        for(int i = 1; i < m+1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            list[u-1].add(v-1); // 1~n까지라서 인덱스인 0~n-1에 넣으려고 -1 해줌
            list[v-1].add(u-1);
        }
        
        for(int i = 0; i < n; i++) {    
            if(!visited[i]) {    // 이미 수행한 그래프 요소는 넘어가고, 다음 그래프가 있다면 수행됨    
                DFS(i);    // DFS 끝까지 수행하면 연결 요소 +1
                component++;
            }
        }
        bw.write(component+"");
        bw.flush();
        bw.close();
    }
    
    static void DFS(int a) {
        visited[a] = true;    // 방문 처리
        
        for(int val : list[a]) {
            if(!visited[val]) {
                DFS(val);
            }
        }
    }
 
}

 

 

 

---