백준 24479 자바

 

DFS 문제이고 전에 푼 bfs 문제와 유사합니다.

DFS는 재귀를 이용하기 때문에 풀이가 좀 간단해지네요.

 

아래  DFS에 대해 설명하자면

check[] 배열은 방문을 했는지, 안 했는지를 확인하고

arr[] 배열은 방문 순서를 담는 배열입니다.

 

입력을 보면

1 - 2 4

2 - 1 3 4

3 - 2 4

4 - 1 2 3

이렇게 ArrayList가 만들어지고

노드는

      1

   2    4

      3

이런 식으로 만들어집니다.

 

먼저 start로 1이 들어오면, for문에서 i는 list[1]의 2,4를 확인합니다.

1. if (!check[2]) 이므로 DFS(2)를 불러옵니다. 그럼 DFS(2)가 실행되면서 arr[2] 는 2가 되겠죠.

2. for문이 int i : list[2] (3,4)를 돌게 되고 3을 먼저 가니까 3이 3번째, 4가 4번째가 됩니다.

 

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]);
        }
            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);
            }
        }
      }
    }