[코드트리] 연결된 그래프 2 (DFS) - JAVA

알고리즘 스터디 - DFS

https://www.codetree.ai/training-field/search/problems/connected-graph-2/description?page=1&pageSize=20&tags=DFS&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

# 문제

# 예제

입력

4 3
1 4
2 4
3 4

 

출력

1 2 3

 

# 필요개념

이 문제에서 요구하는 것은 가장 많은 정점으로 갈 수 있는 노드를 출력하는 것이다. 이는 dfs 연산의 횟수와 관련이 있는데, dfs가 일어날 때마다 카운트를 해주면 얼마나 많은 정점으로 이동할 수 있는지 알 수 있다.

 

dfs에서는 카운트를 반환해주어 이를 저장해주어야 하는데, 나는 n * 2 크기의 배열을 생성하여 [n][0]에는 노드번호를, [n][1]에는 카운트한 개수를 넣어주었다. 이를 배열에 넣어준 이유는 내림차순 정렬을 하기 위함이다.

 

 

Comparator<>

객체를 정렬할 때 사용하고,<> 안에는 타입을 넣어준다. 이차원 배열의 경우 일차원배열을 일차원 배열에 넣은 모양새를 생각하면 되기 때문에 int[]를 넣어주었다.

cnt가 같다면, 노드번호를 오름차순 형태로 정렬하고, 다르다면 cnt를 내림차순으로 정렬할 수 있도록 코드를 작성하였다.

 

 

정렬 후 가장 앞에 있는 cnt가 가장 큰 cnt일 것이기 떄문에, maxCnt와 같은 cnt를 갖는 인덱스를 스트링 빌더에 넣어주어싿.

 

 

# Code

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

public class Main {
    static int n;
    static int cnt = 0;
    static ArrayList<Integer>[] arr;
    static boolean[] isVisit;

    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new ArrayList[n];

        for (int i = 0 ; i < n ; i++) { // 배열에 리스트 생성
            arr[i] = new ArrayList<>();
        }
        
        for (int i = 0 ; i < m ; i++) { // 리스트에 값 넣기
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            arr[idx - 1].add(val);
        }
        int[][] answer = new int[n][2]; // 노드마다 연결된 노드개수 담는 배열 생성
        for (int i = 0 ; i < n ; i++) {
            isVisit = new boolean[n];
            cnt = 0;
            int a = dfs(i + 1);
            answer[i][0] = i + 1;
            answer[i][1] = a;
        }

        Arrays.sort(answer, new Comparator<int[]>() { // cnt 내림차순, 값 오름차순
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                } else {
                    return o2[1] - o1[1];
                }
            }
        });
        int max = answer[0][1];
        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < n ; i++) {
            if (max == answer[i][1]) {
                sb.append(answer[i][0] + " ");
            }
        }

        System.out.println(sb.toString());

    }
    public static int dfs(int start) {
        isVisit[start - 1] = true;
        cnt++;
        for (int i = 0 ; i < arr[start - 1].size() ; i++) {
            if (!isVisit[arr[start - 1].get(i) - 1]) {
                dfs(arr[start - 1].get(i));
            }
        }
        return cnt;
    }
}

 

# 결과