Java 백준 문제풀이 (51) 연결 요소의 개수

 

간만에 풀어보는 그래프 문제다.

기초가 너무 부족한 것 같아서 한동안 그래프는 거들떠도 안보고 정렬 문제만 풀다가 왔는데, 확실히 그래프 문제를 오랫동안 풀지 않았음에도 예전보다 훨씬 쉽게 느껴진다.

 

우선 혹시나 애초에 문제가 잘 이해되지 않는 사람을 위해 짧게 설명하겠다.

 

위와 같이 생긴 게 그래프고, 문제에서 말하는 연결 요소의 개수란 (0-1-2-3-4-5), (6-7) => 2개 이런 식으로 구하라는 말이다.

혹시 그래프 자체를 모른다면 유튜브로 배우고 오자.

 

이 문제의 전제 조건은 별거 없다.

        // 방향이 없다.
        // 1번째 줄 정점 개수 N, 간선 개수 M
        // 두번째 줄부터 간선의 양 끝점 u, v

방향이 없다는 말은 3에서 5로 갈 수 있으면 5에서도 3으로 갈 수 있다는 뜻이다.

따라서 각 정점의 배열에 간선 정보를 등록할 때, 양 쪽 모두 서로 건너갈 수 있도록 등록해줘야 한다.

 

ex ) 3과 5가 연결된 경우

ArrayList<ArrayList<Integer>> list;

list.get(3).add(5);

list.get(5).add(3);

 

내가 작성한 야매 수도코드를 보자.

수도코드만 보고도 충분히 풀 수 있다.

 

public class Main {
    public static void main(String[] args) throws IOException {
        // 방향이 없다.
        // 1번째 줄 정점 개수 N, 간선 개수 M
        // 두번째 줄부터 간선의 양 끝점 u, v

        // 정점 개수 입력 받기
        // 간선 개수 입력 받기

        // 반복문
        // 간선 정보 입력할 ArrayList 초기화 (정점 수만큼)

        // 반복문 (간선 수만큼)
        // -> 방향이 없기 때문에 각 정점은 서로 상대방의 값을 가진다.
        // -> 따라서 ArrayList.get(u).add(v), ArrayList.get(v).add(u)를 모두 해줘야함.

        // dfs실행 ( 원본 배열, 방문 체크용 배열, 정점 )

        // 정답 출력
    }

    public static void dfs(int vertex, ArrayList<ArrayList<Integer>> arr, boolean[] visited) {
        // 만약 방문했을 경우 return

        // 호출 시 해당 정점은 방문했으므로 true

        // 반복문
        // 해당 정점에 등록된 간선 조회

         // 만약 간선으로 통하는 정점을 아직 방문하지 않았다면 재귀호출
        }
    }
}

 

그렇다.. 야매지만 필요한 내용은 모두 들어가있다.

라고 생각했는데 지금 보니까 어떻게 연결 요소 개수를 체크할 것인지 가장 중요한 게 빠져있다.

 

문제를 똑바로 안 보고 코드를 다 작성한 다음에 뭘 구해야하는지 읽었더니..

dfs 함수에서 방문 시마다 visited를 체크해주고 있으니 외부의 반복문에서도 visited가 아직 false인 정점만 다시 탐색하면 되겠다.

 

벌써 다 말했으니 이제 문제 풀 시간이다.

사실 아니다. 중요한 내용이 하나 남아있다.

나도 이것 때문에 5분만에 풀고 10분동안 방황했는데, 문제 조건을 보면 노드의 개수 N(1<=N<=1000)과 에지의 개수 (0<=M<=N*(N-1)/2)가 주어진다고 적혀있다.

 

이게 무슨 말이냐?

에지가 없는 정점(노드)가 있을 수도 있다는 말이다.

 

예를 들어 N과 M이 (2, 0)이면 어떨까?

정점이 하나만 있더라도 아무튼 연결 요소의 개수는 카운트되어야 하는데, 위에서 작성한 야매 수도코드 기준으로만 코드를 작성한다면 카운트는 0이 나온다.

 

그럼 어떻게 할까요?

알아서 풀어보삼

 

정답은 밑으로

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 방향이 없다.
        // 1번째 줄 정점 개수 N, 간선 개수 M
        // 두번째 줄부터 간선의 양 끝점 u, v
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
 
        // 정점 개수 입력 받기
        // 간선 개수 입력 받기
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        // 반복문
        // 간선 정보 입력할 ArrayList 초기화 (정점 수만큼)
        for (int i=0; i<=N; i++) {
            list.add(new ArrayList<>());
        }
 
        // 반복문 (간선 수만큼)
        // -> 방향이 없기 때문에 각 정점은 서로 상대방의 값을 가진다.
        // -> 따라서 ArrayList.get(u).add(v), ArrayList.get(v).add(u)를 모두 해줘야함.
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
 
            list.get(n).add(k);
            list.get(k).add(n);
        }
 
        // dfs실행 ( 원본 배열, 방문 체크용 배열, 정점 )
        boolean[] visited = new boolean[N+1];
        int answer = 0;
        for (int i=0; i<list.size(); i++) {
            if (list.get(i).isEmpty()) answer++;
            for (int j=0; j<list.get(i).size(); j++) {
                if (!visited[list.get(i).get(j)]) {
                    dfs(list.get(i).get(j), list, visited);
                    answer++;
                }
            }
        }
 
        // 정답 출력
        System.out.println(answer-1);
    }
 
    public static void dfs(int vertex, ArrayList<ArrayList<Integer>> arr, boolean[] visited) {
        if (visited[vertex]) return;
 
        // 호출 시 해당 정점은 방문했으므로 true
        visited[vertex] = true;
 
        // 해당 정점에 등록된 간선 조회
        for (int i = 0; i < arr.get(vertex).size(); i++) {
            int next = arr.get(vertex).get(i);
 
            // 만약 간선으로 통하는 정점을 아직 방문하지 않았다면 재귀호출
            if (!visited[next]) {
                dfs(next, arr, visited);
            }
 
        }
    }
}
 

 

난 수도코드를 처음에 한 번만 작성하고 이후로는 추가하거나 고치지 않는다.

수도코드는 무시하고 읽자.