11724번 : 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        visited = new boolean[n+1];

        //그래프 초기화
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<Integer>());
        }

        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            g.get(a).add(b);
            g.get(b).add(a);
        }
        int result=0;
        for(int i=1;i<=n;i++) {
            if(dfs(i)) result++;
        }

        bw.write(result + "");
        bw.flush();
    }

    public static boolean dfs(int x) {
        boolean flag = false;
        if(!visited[x]) {
            visited[x] = true;
            flag = true;
        }

        for(int i=0;i<g.get(x).size();i++) {
            int y = g.get(x).get(i);
            if(!visited[y]) {
                dfs(y);
            }
        }
        return flag;
    }
}

 

 

해결방법

첫 번째 시도: DFS를 구현하여 문제를 풀었는데 틀렸다. => 코드를 잘못 구현했다. 

두 번째 시도: 바꿔서 냈는데 또 틀렸다. => 무방향 그래프인데 방향 그래프로 만들었다.

세 번째 시도: 정답

 

첫 번째 시도는 flag를 true로 설정하는 위치가 옳지 못 하여서 아래와 같은 입력이 들어왔을 때 틀리게 나온다.

1 1       2 1
1 1       1 1
=> 0     =>0

 

두 번째 시도는 첫 번째 시도의 코드를 수정하여 위 입력이 들어왔을 때 결괏값이 잘 나오는데 백준에선 틀렸다고 해서 뭐가 문제인지 몰랐다. 문제에 무방향 그래프라고 떡하니 나와있는데 방향 그래프로 만들어서 틀린 것이다. 이를 수정해 문제를 해결하였다. 아직 많이 부족한 것 같다.