[백준] 11724번 - 연결 요소의 개수 (Java)(◎)

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

11724번: 연결 요소의 개수

<문제 분석>

1. 연결 요소의 개수는 연결된 정점 그룹의 개수라고 생각하면 된다. 

2. 방향성이 없는 그래프이므로 인접행렬로 받도록 하자.

 

 

<문제 풀이 #1>

1. 그룹화를 만드는 것이 관건이다. 메인함수에서 dfs를 호출할 때 for문을 돌려서 정점 1번부터 N번까지 돌면서 호출하자.

2. 방문배열 visited[]를 적극 활용해서 이미 방문한 정점은 스킵하자. 조건문은 심플하게.

 

 

<코드 구현 #1>

import java.util.*;

/*
백준 11724번 : 연결 요소의 개수
*/

public class Main {
    static int N, M;
    static int A[][];
    static boolean visited[];

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        A = new int[N+1][N+1];
        for (int i=0; i<M; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            A[s][e] = 1;
            A[e][s] = 1;
        }
    }

    void DFS(int v) {
        visited[v] = true;

        // v번째 정점을 기준으로 탐색을 한다.
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;
            if (A[v][i] == 0) continue;
            DFS(i);
        }
    }

    void Solve() {
        visited = new boolean[N+1];
        int count = 0;
        // 정점 1번부터 N번까지 탐색 출발을 한다. 
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;
            DFS(i);
            count++;
        }
        System.out.println(count);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

 

<풀이 #2>

DFS 탐색 시의 전개과정이다.

연결된 정점들을 방문할 때마다 방문배열을 업데이트 해준다.

탐색 전 방문배열을 확인해서 이미 방문한 곳이면 스킵한다.

연결된 정점들은 한번 다 순회하면 DFS 탐색이 종료된다.

따라서, DFS 탐색 실행 횟수가 연결요소 갯수와 동일하다.

 

<구현 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int N, M;
    static ArrayList<Integer> list[]; //인접리스트 방식
    static boolean visited[];

    void DFS(int s) {
        visited[s] = true;
        for (int e : list[s]) {
            if (visited[e]) continue;
            DFS(e);
        }
    }

    void BFS(int s) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(s);
        visited[s] = true;

        while (!Q.isEmpty()) {
            int now = Q.poll();
            for (int next : list[now]) {
                if (visited[next]) continue;
                Q.offer(next);
                visited[next] = true;
            }
        }
    }

	void Solve() {
        int count = 0;
        visited = new boolean[N+1];
        // 한번 순회가 되는 서클이 연결요소이다.
        // DFS/BFS 탐색이 종료되었다는 것은 더이상 연결된 정점이 없다는 뜻이다.
        // 즉, 그래프 탐색 횟수 == 연결요소 개수 이다
        for (int i=1; i<=N; i++) {
            if (visited[i]) continue;
            //DFS(i);
            BFS(i);
            count++;
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {//노드번호가 1부터라서 1부터 할당함
            list[i] = new ArrayList<Integer>();
        }
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(e);
            list[e].add(s);
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<제출 결과)

1) DFS 탐색 결과

2) BFS 탐색 결과

BFS 탐색 시에 약간의 실행시간이 절약되지만 큰 차이는 없다.