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

💡문제 분석 요약

방향없는 그래프의 간선 정보를 입력받아, 연결 요소를 출력하는 문제이다.

• 시간 제한: 3초
• 메모리 제한: 512MB

 

💡알고리즘 설계

• boolean[][] graph 에 그래프 간선 정보를 저장한다. (양방향)
• 모든 정점을 순회하며 방문 여부 검사
  • 해당 정점을 방문하지 않은 경우 (visited[i] = false)
    • dfs 메서드 호출한다.
    • 연결 요소 개수(count)를 증가시킨다.
• dfs 메서드
  • 현재 정점을 방문 처리한다.
  • 해당 정점과 연결된 정점이 아직 방문하지 않은 경우 (graph[index][i] && !visited[i])
    • 해당 정점을 재귀적으로 dfs 호출한다.

 

💡코드

import java.io.*;

public class Main {
    static int n, k;
    static boolean[] visited;
    static boolean[][] graph;

    static void dfs(int index) {
        visited[index] = true;
        for(int i=1; i<=n; i++) {
            if(graph[index][i] && !visited[i])
                dfs(i);
        }
    }

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

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        graph = new boolean[n+1][n+1];
        visited = new boolean[n+1];
        for(int i=0; i<k; i++) {
            str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            graph[x][y] = graph[y][x] = true;
        }

        int count = 0;
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                dfs(i);
                count++;
            }
        }

        System.out.println(count);
    }
}

 

💡시간복잡도

$O(N^2)$

 

💡 느낀점 or 기억할정보

DFS를 인접 행렬을 이용해서 풀 수 있다는 것에 조금 익숙해진 것 같다. 조금 더 난이도 있는 DFS 문제가 나오면 또 헷갈릴 수도 있을 것 같아서 문제를 많이 풀어봐야할 것 같다.