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

문제

정점(node | N)와 간선의 개수(edge | M)이 주어진다.

간선의 개수만큼 입력이 들어온다.

각각 시작점 - 도착점으로 주어진다.

다 연결하고 덩어리로 연결된 애들끼리 묶어서, 총 몇 묶음인지 구하라.

 

문제 링크 : https://www.acmicpc.net/problem/11724

---

원리

그래프 탐색( DFS )

 

---

풀이방법

1. 반복을 통해 연결된 노드를 Set으로 묶고, Set의 개수 구하기(ArrayLsit + HashSet) [ 로컬 성공, 백준 실패 ]

2. DFS를 이용한 탐색

---

나의 코드

1. 반복을 통해 연결된 노드를 Set으로 묶고, Set의 개수 구하기(ArrayLsit + HashSet) [ 로컬 성공, 백준 실패 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class no11724 {

    static ArrayList<HashSet<Integer>> list;

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

        list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int node = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());

        while (edge-- > 0) {
            StringTokenizer edgeSt = new StringTokenizer(br.readLine(), " ");
            // 최초엔 아무 Set도 없으므로, 첫 줄의 간선으로 Set 만들어줌
            if (list.isEmpty()) {
                HashSet<Integer> set = new HashSet<>();
                set.add(Integer.parseInt(edgeSt.nextToken()));
                set.add(Integer.parseInt(edgeSt.nextToken()));
                list.add(set);
            } else {
                int start = Integer.parseInt(edgeSt.nextToken());
                int end = Integer.parseInt(edgeSt.nextToken());
                checkList(start, end, node);
            }
        }

        System.out.println(list.size());
    }

    private static void checkList(int start, int end, int node) {
        boolean check = false; // 다른 셋에 들어갔는지 확인. 안들어 갔다면 새로운 셋을 만들어 리스트에 담아줘야하기 때문
        int save = node; // 아무리 set가 늘어나도 node수보다 많진 않을거임

        // 각각의 Set를 넣어둔 list를 순회
        for (int i = 0; i < list.size(); i++) {
            // 입력된 노드가 현재 선택한 Set에 요소로 존재할 때,
            if (list.get(i).contains(start) || list.get(i).contains(end)) {
                // 만약 그 전에 다른 Set에도 있었다면, 이전 Set과 현재 Set을 합병
                if (save != node) {
                    list.get(save).add(list.get(i).iterator().next());
                    list.remove(i);
                }
                // 만약 그 전에 다른 Set에 없었다면, 현재 Set에 두 정점 중 없는 애를 넣어줌
                else {
                    list.get(i).add(start);
                    list.get(i).add(end);
                    save = i;
                }
            }
            // 끝까지 다 돌았는데 아무 Set에도 포함이 안되면 체크
            if (i==list.size()-1 && save==node) check = true;
        }

        // 모든 Set를 다 돌고 미포함이면, 새로 Set를 만들어 넣어주고 합병
        if (check) {
            HashSet<Integer> set = new HashSet<>();
            set.add(start);
            set.add(end);
            list.add(set);
        }
    }
}

2. DFS를 이용한 탐색

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

public class no11724 {
    
    static Integer node;
    static Integer edge;
    static int [][] matrix;
    static boolean [] visited; 
    

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        
        matrix = new int[node+1][node+1];
        visited = new boolean[node+1];
        
        // 행렬에 연결되는 노드에 1으로 체크(방향이 없으므로 양방향 1체크) 
        for(int i=0; i<edge; i++) {
            StringTokenizer edgeSt = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(edgeSt.nextToken());
            int end = Integer.parseInt(edgeSt.nextToken());
            matrix[start][end] = 1;
            matrix[end][start] = 1;
        }
        
        int count = 0;
        
        // 방문한 열을 돌면서, 안가본 정점이 있으면 탐색을 시작하고, 덩어리수 +1
        for(int i=1 ; i<=node ; i++) {
            if(!visited[i]) {
                DFS(i);
                count++;
            }
        }
        
        System.out.println(count);
    }
    
    private static void DFS (int start) {
        // 방문 체크
        visited[start] = true;
        
        // 방문한 행을 돌면서, 간선이 연결된 애들에 한해서, 안가본 곳이면 가봐라
        for(int i =1; i<=node ; i++) {
            if(matrix[start][i]==1 && !visited[i]) DFS(i);
        }
    }
}

 

---

레퍼런스 코드

참고 링크 : https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11724%EB%B2%88-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C%EC%9D%98-%EA%B0%9C%EC%88%98-%EC%9E%90%EB%B0%94Java