백준 24480 자바

 

 

 

새해 기념으로 한 문제만 풀겠습니다.. 술 먹고 와서 너무 힘듭니다..

전에 풀었던 DFS문제이고 내림차순으로만 변경해주면 됩니다.

 

1 - 4 2

2 - 4 3 1

4 - 4 2

4 - 3 2 1

내림차순을 하면 이런 식으로 Arraylist에 넣어집니다.

 

그럼 노드는

     1

4       2

    3

 

이렇게 형성된다고 치면 순서는

1 - 1번째

2 - 4번쨰

3 - 3번째

4 -  2번째

5 - 0

이렇게 연결이 됩니다. 직접 그려서 해보시면 이해가 쉽습니다.

인접 정점을 내림차순으로 방문하니까

1에서 연결된 4, 2에서 4를 먼저 방문을 하고, 4와 연결된 3, 2중에서는 3을 먼저 방문을 합니다.

그리고 나머지 2를 방문하게 됩니다.

 

import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Integer>[] list;
    static boolean[] check;
    static int N, M, R;
    static int[] arr;
    static int cnt = 0;

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

         list = new ArrayList[N+1];
         check = new boolean[N+1];
         arr = new int[N+1];

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

          list[a].add(b);
          list[b].add(a);
        }

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

        for (int i = 1; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
      }
      public static void DFS(int start) {
        check[start] = true;
        arr[start] = ++cnt;

        for (int i : list[start]) {
            if (!check[i]) {
                DFS(i);
            }
        }
      }
    }