DFS 구현하기 (백준 24479번)

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

처음엔 스택으로 구현했지만 시간초과로 계속 실패했다.
다른 사람의 재귀코드를 넣어봤더니 성공했다.

스택이 재귀보다 빠르다고 들었는데 재귀 코드가 내 코드와 크게 다르지 않은 반복을 하는데 실패를 해서 스택의 사용법이 잘못됐다고 생각했다.

방문한 원소를 스택에서 제거하지 않고 방문처리를 해서 스택이 비효율적으로 처리된 것으로 보인다. 또한 인접 리스트를 사용해서 많은 양의 데이터가 들어오는 코딩테스트에서는 인접 배열을 쓰는 것이 좋을 것 같다.

package BOJ.DFS;

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

//https://www.acmicpc.net/problem/24479
public class BOJ_24479 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 정점의 수
        int M = Integer.parseInt(st.nextToken());; // 간선의 수
        int R = Integer.parseInt(st.nextToken());; // 시작 정점

        int visited[] = new int[N+1]; // 정점 수 +1 만큼 (1~N이라서) 방문 여부 배열

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for(int i=0;i<=N;i++){ // N+1개의 정점 생성 (0 때문)
            graph.add(new ArrayList<>());
        } // 0~N 까지 생성

        for(int i=0;i<M;i++){ // 간선 입력 받는 부분
            StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st2.nextToken());
            int end = Integer.parseInt(st2.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
            // 방향이 없는 무방향 간선이기 때문에 양쪽으로 이어준다.
        }

        for(int i=1;i<=N;i++){
            Collections.sort(graph.get(i),Collections.reverseOrder()); // 내림차순 정렬 -> 오름차순으로 빼야하기 떄문
        }
        dfs(R,visited,graph);

        for(int i=1;i<=N;i++){
            sb.append(visited[i]).append("\n");
        }
        System.out.println(sb);

    }

    // 시작 정점을 stack에 넣는다
    // index = stack.pop()
    // index와 인접한 정점 중 방문하지 않은 정점을 모두 stack 에 넣는다
    // 반복
    public static void dfs(int start,int visited[],ArrayList<ArrayList<Integer>> graph){
        Stack<Integer> stack = new Stack<>();
        int seq = 1;
        stack.push(start);
        int index = start;

        while(!stack.isEmpty()){
            index = stack.pop(); // 주변 원소 탐색을 위해
            if(visited[index] !=0) continue; // 이미 방문한 원소면 처음으로

            visited[index] = seq++;
            for(int i=0;i<graph.get(index).size();i++){
                if(visited[graph.get(index).get(i)]==0)
                    stack.push(graph.get(index).get(i));
            }

        }
    }
}