[백준] 알고리즘 수업 - 깊이 우선 탐색 2 (24480번)

문제 힌트

1. 자료구조

• List<Integer>[] (그래프 표현)
  • 정점 간의 간선을 표현하기 위해 인접 리스트를 사용합니다.
  • 이유: 정점과 간선의 수가 크기 때문에 인접 행렬을 사용하면 공간 복잡도가 매우 비효율적입니다. 인접 리스트를 통해 필요한 간선 정보만 저장해 메모리를 절약할 수 있습니다.
• int[] (방문 순서 기록)
  • 방문 순서를 저장하기 위해 배열을 사용합니다.
  • 이유: 정점 번호와 배열의 인덱스를 매칭하여 빠르게 방문 순서를 기록할 수 있습니다. 배열을 통해 O(1) 시간에 순서를 조회하거나 설정할 수 있습니다.
• Collections.sort (내림차순 정렬)
  • 문제에서 요구하는 인접 정점을 내림차순으로 방문을 구현하기 위해 사용합니다.
  • 이유: 탐색 전에 인접 리스트를 내림차순으로 정렬함으로써 DFS 수행 중 자연스럽게 내림차순 순서를 유지할 수 있습니다.

 

2. 핵심 아이디어

1. DFS를 통한 깊이 우선 탐색
   • 현재 정점에서 갈 수 있는 모든 인접 정점을 탐색하고, 재귀적으로 다음 정점을 방문합니다.
   • 방문할 때마다 방문 순서를 기록하며, 이미 방문한 정점은 재방문하지 않습니다.
2. 인접 정점을 내림차순으로 정렬
   • DFS 수행 전에 각 정점의 인접 리스트를 내림차순으로 정렬합니다.
   • 이렇게 하면 탐색 도중 따로 정렬 작업을 하지 않아도 문제의 요구사항을 만족합니다.
3. 방문 불가능한 정점 처리
   • 방문할 수 없는 정점은 방문 순서가 0으로 초기화된 상태를 유지합니다.
   • 초기 배열을 0으로 설정해 방문하지 않은 정점을 명확히 구분합니다.

 

3. 로직

1. 그래프 초기화
   • 정점과 간선 정보를 입력받아 인접 리스트로 그래프를 생성합니다.
   • 각 정점의 인접 정점을 리스트에 추가하며, 이후 내림차순으로 정렬합니다.
2. DFS 탐색 시작
   • 시작 정점을 방문하고 순서를 기록합니다.
   • 재귀적으로 인접 정점을 탐색하며, 방문 순서를 기록합니다.
3. 결과 출력
   • 모든 정점에 대해 방문 순서를 출력합니다.
   • 방문하지 못한 정점은 0으로 표시됩니다.

 

 

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static int M;

    static int[] visitedOrder;
    static List<Integer>[] graph;

    static StringBuilder sb = new StringBuilder();
    static int order = 1;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        graph = new List[N+1];
        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        visitedOrder = new int[N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            graph[n1].add(n2);
            graph[n2].add(n1);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i], Collections.reverseOrder());
        }

        visitedOrder[start] = order++;
        dfs(start);

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

        System.out.println(sb);
    }

    public static void dfs(int node) {
        for (int next : graph[node]) {
            if (visitedOrder[next] == 0) {
                visitedOrder[next] = order++;
                dfs(next);
            }
        }
    }
}