백준 - 연결 요소의 개수(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 :https://www.acmicpc.net/problem/11724

 

[문제 설명]

그래프가 총 몇개인지 구하시오.

 

[접근 방법]

노드들을 모두 입력 받은 후, 탐색을 통하여 그래프 하나를 전부 순회하면 개수를 하나 추가하는 방법으로 풀었다.

그래프를 BFS로 모두 순회하므로 시간복잡도는 O(N+M). 공간복잡도도 인접행렬로 구현할 경우 O(N^2)이라, 연결리스트로 구현해서 O(N+M)가 된다.

 

결론 : 시간 복잡도 O(N+M) 공간복잡도 O(N+M)

 

[내 답안 수정하기]

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


public class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int cntOfNode = Integer.parseInt(st.nextToken());
        int cntOfEdge = Integer.parseInt(st.nextToken());
        List<Integer>[] graph = new LinkedList[cntOfNode];
        boolean[] isVisitedCity = new boolean[cntOfNode];

        for (int i = 0; i < cntOfEdge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int idxOfStartCity = Integer.parseInt(st.nextToken())-1;
            int idxOfEndCity = Integer.parseInt(st.nextToken())-1;

            if (graph[idxOfStartCity] == null) {
                graph[idxOfStartCity] = new LinkedList<>();
            }
            graph[idxOfStartCity].add(idxOfEndCity);

            if (graph[idxOfEndCity] == null) {
                graph[idxOfEndCity] = new LinkedList<>();
            }
            graph[idxOfEndCity].add(idxOfStartCity);
        }

        // 혼자 있는 노드(외딴섬) 개수 추가하기
        for (int i = 0; i <cntOfNode; i++) {
            if (graph[i] == null) {
                answer++;
            }
        }

        for (int i = 0; i < cntOfNode; i++) {
            List<Integer> route = graph[i];
            // graph[i]를 이미 체크했으면 null이 되므로 다음 그래프
            if (route == null || route.size() == 0) {
                continue;
            }
            isVisitedCity[i] = true;

            // 현재 그래프 전체 탐색
            Queue<List<Integer>> q = new LinkedList<>();
            q.offer(route);
            while (!q.isEmpty()) {
                List<Integer> children = q.poll();
                for (int j = 0; j < children.size(); j++) {
                    if (!isVisitedCity[children.get(j)]) {
                        q.offer(graph[children.get(j)]);
                        isVisitedCity[children.get(j)] = true;
                    }
                }
                children.clear();
            }

            route.clear();
            answer++;
        }
        System.out.println(answer);
    }
}

 

그래프가 익숙하지 않아서인지 코드를 작성하는데 시간이 굉장히 많이 뺏긴다.

좀 많이 풀어야 익숙해지지 않을까 싶다.