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

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

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

문제

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)
정점의 번호는 1 ~ N번, 모든 간선의 가중치는 1

=> 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서?

입력
첫째 줄: 정점의 수 N (5 <= N <= 100,000), 간선의 수 M (1 <= M <= 200,000), 시작 정점 R (1 <= R <= N)
다음 M개의 줄에 간선 정보 u, v 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타냄(1 <= u < v <= N, u != v)
모든 간선의 (u, v) 쌍의 값은 서로 다름
출력
첫째 줄부터 N개 줄에 정수를 한 개씩 출력
i번째 줄에는 정점 i의 방문 순서를 출력
시작 정점의 방문 순서는 1/ 시작 정점에서 방문할 수 X 경우는 0 출력

---

풀이

• `graph[i]`: i번 정점과 연결된 정점 목록
• `visited[i]`: i번 정점 방문 여부
• `order[i]`: i번 정점이 몇 번째로 방문됐는지

 

• 그래프 초기화 및 인접 리스트 구성
  • 양방향 간선

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

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());

    graph[u].add(v);
    graph[v].add(u); 
}

 

• DFS
  • 현재 `node` 방문 -> `order[node]`에 방문 순서 기록

public static void dfs(int node) {
    visited[node] = true;
    order[node] = cnt++;

    for (int next : graph[node]) {
        if (!visited[next]) dfs(next);
    }
}

---

예시

5 5 1 / 1 4 / 1 2 / 2 3 / 2 4 / 3 4

 

그래프

• 1 : [2, 4]
• 2 : [1, 3, 4]
• 3 : [2, 4]
• 4 : [1, 2, 3]
• 5 : [] (연결 X)

-> DFS 순서: 1 -> 2 -> 3 -> 4 (-> 5 방문 X)

---

코드

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

// 알고리즘 수업 - 깊이 우선 탐색 1
public class boj_24479 {
    static int N, M, R;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] order;
    static int cnt = 1;

    public static void dfs(int node) {
        visited[node] = true;
        order[node] = cnt++;

        for (int next : graph[node]) {
            if (!visited[next]) dfs(next);
        }
    }

    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();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

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

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

        dfs(R);

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