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

 

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

 

---

문제

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], Collections.reverseOrder());
        }

        dfs(R);

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

 

바로 전에 올렸던 24479 알고리즘 수업 - 깊이 우선 탐색 1번에서 조금만 변형하면 되는 문제이다.

 

24479는 오름차순으로 탐색하고 24480은 내림차순으로 탐색한다.

 

24479번에서 오름차순으로 정렬하는 부분을 내림차순으로 정렬하기만 하면 완성된다.

 

https://gamja00.tistory.com/149

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