[240302] 알고리즘 리부트 22일차 - 백준 24479 자바

- 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1

엄청난 시간과 메모리이다. DFS 문제를 푼 지 오래되었지만 찾아보지 않고 직접 구현해보고자 했다. 인접배열로 만들 경우 당연 n과 m의 크기 때문에 메모리를 초과할 것 같았고 어차피 배열로 순회하면 시간도 초과해버린다고 생각했다. 정점에 비해 간선이 적을 경우에는 배열보다 인접리스트를 쓰는 것이 유리하다고 기억했고 이를 활용해 구현했다. 

순회하는 정점의 순서대로 값을 넣기 위해 order 배열을 생성하고 idx를 dfs 함수를 호출할 때마다 하나씩 증가시켜 값으로 넣도록 처리했다. 처음에는 dfs인자에 담아서 처리하려 했는데 같은 정점에서 뻗어나가는 간선의 경우 동일한 idx를 갖게 되어 순서가 중복되는 문제가 발생했었다. 이 코드가 최적인 것 같지는 않아서 다시 DFS를 공부하고 구현해보려 한다.

import java.io.*;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static int idx = 0;
    public static int[] order;
    public static ArrayList[] list;
    public static boolean[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

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

        list = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }

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

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list[s].add(e);
            list[e].add(s);

        }

        br.close();

        for (int i = 0; i <= n; i++) {
            Collections.sort(list[i]);
        }


        dfs(r);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= n; i++) {
            bw.write(order[i] + "\n");
        }

        bw.flush();
    }

    private static void dfs(int r) {
        ++idx;
        visited[r] = true;
        order[r] = idx;
        //System.out.println("r: "+r);
        //System.out.println("idx: "+idx);

        for (int i = 0; i < list[r].size(); i++) {
            if (!visited[(int) list[r].get(i)]) {
                //System.out.println("여기로떠남: "+ list[r].get(i).toString());
                dfs((int) list[r].get(i));

            }
        }
    }
}