JAVA 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 (그래프)

 

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

---

문제

1. 첫째 줄에 정점 개수 N ( 5 <= N <= 100000), 간선의 수 M ( 1 <= M <= 200000), 시작 정점 ( 1 <= R <= N) 이 주어진다.
2. 둘째 줄부터 M개의 줄에 간선의 정보 u v ( 1 <= u < v <= N, u != v) 가중치 1인 양방향 간선이 주어진다.
3. 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력하는데 i번쨰 줄에 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서를 1로 시작하며, 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
4. 방문 순서는 오름차순으로 방문하도록 한다.

---

 

최종 코드

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

public class Main {
    public static int[] visited;
    public static ArrayList<Integer>[] list;
    public static int count = 1;

    public static void dfs(int s) {
        visited[s] = count++;

        for (int i = 0; i < list[s].size(); i++) {
            if (visited[list[s].get(i)] == 0) {
                dfs(list[s].get(i));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

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

        for (int i = 1; i < N + 1; i++) {
            list[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());

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

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

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

 

 

단순히 dfs 알고리즘을 사용하여 출력하면 된다.

 

오름차순으로 방문해야 되기 때문에 모든 간선을 리스트에 삽입한 후에 각 리스트 별 오름차순 정렬을 실행한다.

 

각 정점 순서대로 방문 순서를 출력해야 되기 때문에 노드의 방문 여부를 보통 boolean 배열로 확인하지만 순서를 출력해야 되므로 int 배열로 바꾸어 각 노드의 방문 순서를 int 배열에 저장하도록 하였다.