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

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

11724번: 연결 요소의 개수

처음에는 dfs 부분을 다음과 같이 작성했다.

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

 

즉 i를 1부터가 아니라 start + 1부터로 지정해줬는데, 이러면 안된다. 다음을 입력하면 잘못된 값이 나온다.

3 2
1 3
3 2

 

직접 그려서 생각해보면 금방 이해할 수 있다. 1에서 2로 가는 방법은 3을 통해서 갈 수 있다. 그런데 i를 start + 1부터 지정해주면, start가 3일 때, 3에서 2로 가는 경로를 탐색하지 못하게 된다. 따라서 i는 1부터 시작해야 한다! 어차피 !visited[i]로 이미 방문한 경로는 pass하기 때문에 i를 1부터 지정해줘도 된다.

 

아래는 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: O(V + E) = 1,000 + 1,000*999*2
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int m;
    static boolean[][] map;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            map[n1][n2] = true;
            map[n2][n1] = true;
        }

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

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