[자바] 백준 24479 & 24480번 알고리즘 수업 - 깊이 우선 탐색 1 & 2

https://www.acmicpc.net/problem/24479

https://www.acmicpc.net/problem/24480

 

DFS를 자바로 구현해본 적이 없어서 푼 가장 기초적인 DFS 문제 ! ArrayList<ArrayList<Integer>> 로 이차원 배열을 선언해서 푼다는 걸 잘 알아두면 될 것 같다!

 

[새로 알게 된 것]

• Collections.sort() 로 오름차순 정렬 가능
• Collections.sort(ArrayList, Collections.reverseOrder()) 로 내림차순 정렬 가능

// 24479번
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    public static int[] visited;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    // 순서 저장을 위한 변수
    public static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        visited = new int[n+1];

        // 그래프 초기화
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }

        // 그래프에 값 넣기
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 오름차순 정렬하기 (한 정점에 대해서)
        for(int i = 1; i <= n; i++){
            Collections.sort(graph.get(i)); // 정점은 1부터 시작하니까..
        }

        // dfs
        count++;
        dfs(r);

        for(int i = 1; i < visited.length; i++){
            bw.write(String.valueOf(visited[i] + "\n" ));
        }
        bw.flush();
        bw.close();
    }
    public static void dfs(int r){
        visited[r] = count;
        for(int i = 0; i < graph.get(r).size(); i++){
            int v = graph.get(r).get(i);
            if(visited[v] == 0){
                count++;
                dfs(v);
            }
        }
    }
}

// 24480번
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    public static int[] visited;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    // 순서 저장을 위한 변수
    public static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        visited = new int[n+1];

        // 그래프 초기화
        for(int i = 0; i <= n; i++){
            graph.add(new ArrayList<Integer>());
        }

        // 그래프에 값 넣기
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 내림차순 정렬하기 (한 정점에 대해서)
        for(int i = 1; i <= n; i++){
            Collections.sort(graph.get(i), Collections.reverseOrder());
        }

        // dfs
        count++;
        dfs(r);

        for(int i = 1; i < visited.length; i++){
            bw.write(String.valueOf(visited[i] + "\n" ));
        }
        bw.flush();
        bw.close();
    }
    public static void dfs(int r){
        visited[r] = count;
        for(int i = 0; i < graph.get(r).size(); i++){
            int v = graph.get(r).get(i);
            if(visited[v] == 0){
                count++;
                dfs(v);
            }
        }
    }
}