[BOJ 24479] 알고리즘 수업 - 깊이 우선 탐색 1 (Java)

 

DFS 의 기본 문제이지만, 함정이 숨어있습니다.

보다시피 정점의 수와 간선의 수가 크다보니 인접행렬을 만들게 되면 메모리 및 시간 초과가 나게 됩니다.

따라서 인접 리스트로 만들어주어야 하고,

문제에서 인접 정점은 오름차순으로 방문한다고 했으니

리스트에 값을 넣은 후 Collections.sort 를 이용하여 오름차순으로 정렬해주어야 한다.

R부터 시작해야 한다는 것도 잊지 말자.

 

 

정답 풀이

package DFS완전정복;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main_BJ_24479_알고리즘수업_깊이우선탐색1 {
    static int N, M, R;
    static int cnt = 1;
    static int[] visited;
    static ArrayList<Integer>[] adjList;
    static StringBuilder sb = new StringBuilder();
    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());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        adjList = new ArrayList[N+1];
        visited = new int[N+1];

        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjList[a].add(b);
            adjList[b].add(a);
        }

        // 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(adjList[i]);
        }

        dfs(R);

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

    private static void dfs(int i) {
        visited[i] = cnt++;
        for (int num: adjList[i]) {
            if (visited[num] == 0) {
                dfs(num);
            }
        }
        }
    }