[DFS] 백준 연결 요소의 개수 11724번

[DFS] 백준 연결 요소의 개수 11724번

---

문제 설명

방향 없는 그래프가 주여졌을 때,

연결 요소의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

(1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

---

출력

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

 

** 풀이 방법

 

정점과 인접 노드를 나타낼 ArrayList와

탐색 여부를 나타낼 boolean 배열을 선언한다.

static ArrayList<Integer>[] A; 
static boolean[] visited;

정점과 간선을 입력 받는다.

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());

 

정점 + 1 크기의 ArrayList 생성정점 +1 크기의 boolean 배열 생성1~n까지 ArrayList를 만들어서각 ArrayList에 m줄에 입력 받은정점 + 인접 노드를 저장한다.

A = new ArrayList[n+1];
visited = new boolean[n+1];
for (int i=1; i<n+1; i++) {
    A[i] = new ArrayList<Integer>();
}

for (int i=0; i<m; i++) {
    st = new StringTokenizer(bf.readLine());
    int s = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    A[s].add(v);
    A[v].add(s);
}

 

1~n까지 방문하지 않은 곳이 있으면count를 1 증가시키고,DFS함수를 호출한다.

모두 탐색이 완료되면 count를 출력시킨다.

int count = 0;
for (int i=1; i<n+1; i++) {
    if (!visited[i]) {
        count++;
        DFS(i);
    }
}
System.out.println(count);

 

public static void DFS(int v) {
    if (visited[v]) return; // 탐색이 완료된 상태면 return
    visited[v] = true; //아니라면 탐색 상태를 true로 변경하고,
    for (int i : A[v]) { // 인접 노드들에 접근해서
        if (visited[i]==false) //탐색 상태가 false인 것들을 재귀적으로 호출한다.
            DFS(i);
    }
}

 

<> 전체 코드 </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
    static ArrayList<Integer>[] A; 
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        A = new ArrayList[n+1];
        visited = new boolean[n+1];
        for (int i=1; i<n+1; i++) {
            A[i] = new ArrayList<Integer>();
        }
        
        for (int i=0; i<m; i++) {
            st = new StringTokenizer(bf.readLine());
            int s = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            A[s].add(v);
            A[v].add(s);
        }
        
        int count = 0;
        for (int i=1; i<n+1; i++) {
            if (!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }
    
    public static void DFS(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (int i : A[v]) {
            if (visited[i]==false)
                DFS(i);
        }
    }
}