[백준] no2606: 바이러스 ☆백준 골드 달성☆

문제

정점(Node)와 간선(연결선/edge)이 주어진다.

각 정점끼리 연결된 애들끼리 그룹화 시킬수 있다.

정점 1에서 시작하여 연결된 정점의 수를 구해라
 
문제 링크 : https://www.acmicpc.net/problem/2606
 

---

원리

1. DFS
2. 그래프탐색

---

풀이방법

DFS : 이번 경우엔 1번에서 출발하는 지점에 한해서 구하는 문제

(경우에 따라 여러 지점에 대해 각 연결된 정점의 수를 구하는 방법으로 변형이 가능하다)

1. 입력된 정점의 좌표마다 이동이 가능하다는표시로 1 표시(그 외엔 0이다)

2. 이때, 방향이 있다면 해당 좌표만, 무방향이라면 뒤집은 좌표도 1로 표기

(예를들어 1-7 연결일 경우, 무방향일 경우 [1,7]과 [7,1] 모두 1로 표시)

3. 방문한 열(low)을 표시할 visited[]을 static으로 생성

4. DFS 시작

5. 들어가면 일단 출발지점은 방문표시

6. 도착지점들을 돌면서 도착지점에서 다시 출발하여 도착할 수 있는 곳에대해 재귀 반복

7. 더이상 도착할 곳이 없으면 재귀 중지됨(visited로 끊기는 구조)

8. 반복을 돌면서 방문한 곳을 set에 담음(set은 중복을 허용하지 않으므로 그냥 넣으면 됨)

 

 

그래프 탐색 : 추후

 

---

나의 코드

1. 특정 노드 번호에 연결된 노드만 알고 싶을 때 (이번 문제의 경우)

private static int node;
    private static int edge;
    private static int[][] matrix;
    private static boolean[] visited; // 방문한 열인지 체크
    private static HashSet<Integer> set = new HashSet<>();

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

        // 초기화 단계
        node = Integer.parseInt(br.readLine());
        edge = Integer.parseInt(br.readLine());
        matrix = new int[node +1][node +1];
        visited = new boolean[node +1];
        for(int i = 0; i< edge; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            Integer low = Integer.parseInt(st.nextToken());
            Integer col = Integer.parseInt(st.nextToken());
            matrix[low][col] = 1;
            matrix[col][low] = 1;
        }

        DFS(1);

//        set.iterator().next(); // 연결된 요소를 모두 출력하고 싶을 때 
        System.out.println(set.size()); // 요소의 개수를 모두 구할 때(만약 처음 값인 1을 포함하고 싶다면, +1 필요) 
    }

    private static void DFS (int start) {
        visited[start] = true;

        for(int i=1 ; i<=node ; i++ ) {
            if(matrix[start][i]==1 && !visited[i]) {
                set.add(i);
                DFS(i);
            }
        }
    }

 

2. 모든 노드에 대해 각각의 그룹에 대한 연결을 묶어서 알고 싶을 때

private static int node;
private static int edge;
private static int[][] matrix;
private static boolean[] visited; // 방문한 열인지 체크
private static HashSet<Integer> set = new HashSet<>();
private static HashMap<Integer, HashSet<Integer>> map = new HashMap<>();

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

    // 초기화 단계
    node = Integer.parseInt(br.readLine());
    edge = Integer.parseInt(br.readLine());
    matrix = new int[node +1][node +1];
    visited = new boolean[node +1];
    for(int i = 0; i< edge; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Integer low = Integer.parseInt(st.nextToken());
        Integer col = Integer.parseInt(st.nextToken());
        matrix[low][col] = 1;
        matrix[col][low] = 1;
    }
    
    int index = 0; 
    for(int i = 1; i<= node; i++) {
        if(!visited[i]) {
            set = new HashSet<>();
            set.add(i);
            DFS(i);
            map.put(index, set);
            index++;
        }
    }
    
    // 각 그룹별 연결 개수 
    for(int i=0 ; i<map.size() ; i++) System.out.println(map.get(i).size()); // 요소의 개수를 모두 구할 때(만약 처음 값인 1을 포함하고 싶다면, +1 필요)
}

private static void DFS (int start) {
    visited[start] = true;

    for(int i=1 ; i<=node ; i++ ) {
        if(matrix[start][i]==1 && !visited[i]) {
            set.add(i);
            DFS(i);
        }
    }
}