본문 바로가기

CS ﹒ Algorithm/Baekjoon

Java 백준 문제풀이(28) 24479: 알고리즘 수업 - 깊이 우선 탐색1 (+24480 깊이 우선 탐색2)

*24480은 내림차순인 것 외 완전히 동일한 문제라서 제일 밑에 정답만 올려놨다.

 

언제 한 번 시간내서 배워야 하는데.. 라고 생각하던 그래프 알고리즘을 찍먹하게 되었다.

쩝.. 생각해보면 예약글이라 이 글이 올라갈 때 쯤에는 어차피 코드 스테이츠에서 그래프 알고리즘 배우는 시기랑 맞물릴 것 같은데 그냥 그 때 공부할 걸 그랬나 싶기도 하다.

 

알고리즘을 처음부터 설명하는 건 너무 오래 걸리고, 이론은 대충 훑고 왔는데 이해 안되는 수준에 맞춰서 글을 작성하였다.

언젠가 그래프 알고리즘에 관한 글도 따로 작성하고 싶다. 

 

바보의 마음은 바보가 아는 법.. 

 

 

 

static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
static boolean[] visited;
static int[] orderCheck;
static int order = 1;

1. ArrayList<ArrayList<Integer>>를 사용하는 이유

- 빠르다.

- 관리가 편하다.

- LinkedList , ArrayList , Array , queue , stack 뭘 써도 되고 그냥 취향이다. 난 ArrayList가 좋더라.

 

2. boolean[] visited

- 해당 정점을 이미 방문했는지 체크한다.

 

3. int[] orderCheck

- 문제에서 N번째 정점을 몇 번째에 방문했는지를 요구하고 있기 때문에 필요하다.

 

4. int order 

- 재귀에서 count역할을 해준다. 이름을 count라고 짓고 위에 배열을 order라고 지을 걸 그랬다.

 

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int vertex = Integer.parseInt(st.nextToken());
    int edge = Integer.parseInt(st.nextToken());
    int start = Integer.parseInt(st.nextToken())-1;

1. start에서 -1을 준 이유

- 배열은 0부터 시작하는데 그래프에서는 재귀 시작 시점에서 이미 1번을 카운트하기 때문에, 배열을 1번부터 시작해서 맞추던지 아니면 문제에서 제시하는 값들을 1씩 빼서 배열 0번과 대응시키던지 해야 한다.

나는 for문에서 1씩 빼준다거나 배열을 1번부터 시작하는 게 더 헷갈려서 이런 방식을 택했다. 맘대로 하면 된다.

 

2. BuffererdReader , StringTokenizer 안 쓰면 통과 안되나요?

- 안해봐서 모름

 

 

for (int i=0; i<vertex; i++) {
    list.add(new ArrayList<>());
}

이론을 훑고 왔으니 알겠지만 2차원 배열이 필요하다. 정점의 개수에 맞춰서 만들어주면 된다.

만약 시작값 1에 대응하고 싶다면 i<=vertex로 만들어야 함.

 

 

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

    list.get(num1).add(num2);
    list.get(num2).add(num1);
    // 무방향 그래프이기 때문에 각 정점에 모두 간선 정보를 입력한다
}

무방향 그래프이기 때문에 {1, 4}를 입력 받았다면 1번도 4번으로 통행할 수 있고 4번 정점에서도 1번 정점으로 통행할 수 있다는 것을 의미한다. 따라서 값을 입력 받으면 해당 정점 모두에게 간선 값을 각각 넣어줘야 한다.

나는 이게 이해가 안되어서 한참 헤맸는데, 너무 별 거 아니라 허탈했다.

또한 시작값을 0에 대응하고 있기 때문에 모든 값에 1을 빼준다.

 

 

for (ArrayList<Integer> arr : list) {
    Collections.sort(arr);
}
visited = new boolean[vertex];
orderCheck = new int[vertex];

문제에서 오름차순으로 방문하라고 적혀있기 때문에 모든 간선 정보를 오름차순으로 입력한다.

input으로 인덱스 크기를 입력 받았으니 배열도 마저 만들어준다.

시작값을 1로 대응하고 싶다면 얘들도 모두 +1을 해줘야 한다.

 

 

dfs(start);

for (int o : orderCheck) {
    System.out.println(o);
}

설명할 게 없다. 그냥 재귀함수 시작 및 결과물 출력.

 

 

 

static void dfs(int r) {
    visited[r] = true;
    orderCheck[r] = order++;
    for (int v : list.get(r)) {
        if (!visited[v]) {
            dfs(v);
        }
    }

마찬가지로 dfs 알고리즘을 훑어보고 왔다면 더이상 설명할 게 없다.

 

 

 

 

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static boolean[] visited;
    static int[] orderCheck;
    static int order = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken())-1; // 0번 부터 시작하게 할 것이다.

        for (int i=0; i<vertex; i++) {
            list.add(new ArrayList<>());
        } // 총 정점의 개수만큼 리스트 내부에 어레이 리스트를 추가

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

            list.get(num1).add(num2);
            list.get(num2).add(num1);
            // 무방향 그래프이기 때문에 각 정점에 모두 간선 정보를 입력한다
        }

        for (ArrayList<Integer> arr : list) {
            Collections.sort(arr);
        } // 오름차순으로 방문해야하기 때문에 모든 간선 정보를 오름차순으로 정렬한다.

        visited = new boolean[vertex];
        orderCheck = new int[vertex];

        dfs(start);

        for (int o : orderCheck) {
            System.out.println(o);
        }
    }

    static void dfs(int r) {
        visited[r] = true;
        orderCheck[r] = order++;
        for (int v : list.get(r)) {
            if (!visited[v]) {
                dfs(v);
            }
        }
        }
    }

완성본

 

 

 

 

 

 

 

++++++ 24480 깊이 우선 탐색 2 정답

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static boolean[] visited;
    static int[] order;
    static int count=0;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        for (int i=0; i<=vertex; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i=1; i<=edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }

        for (int i=1; i<=vertex; i++) {
            Collections.sort(graph.get(i));
            Collections.reverse(graph.get(i));
        }

        visited = new boolean[vertex+1];
        order = new int[vertex+1];

        dfs(start);

        for (int i=1; i< order.length; i++) {
            System.out.println(order[i]);
        }
    }

    static void dfs(int v) {
        count++;
        visited[v] = true;
        order[v] = count;

        for (int a : graph.get(v)) {
            if (!visited[a]) {
                dfs(a);
            }
        }
    }
}

내림차순으로 정렬하는 것 말고는 똑같다.