[백준] 24479, 24480 알고리즘 수업 - 깊이 우선 탐색 1, 2 - 자바

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

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

24479, 24480번 문제는 문제가 거의 비슷하지만 인접 노드에 대해 작은 노드, 큰 노드 중 무엇을 먼저 방문하냐의 차이만 있기 때문에 정정렬 부분만 바꾸어 주면된다. 여기서 같이 다룰 예정이다.

문제 풀이

그래프에 대해 깊이 우선 탐색을 진행했을 때 각 노드가 몇 번재로 방문됐는지 출력하는 문제이다.

 

먼저 연결된 노드가 여러개 있을 때 작은 값의 노드를 먼저 방문하기 때문에 이웃노드를 설정할 때 정렬이 되어야 한다.

0부터 순착탐색을 진행하기 때문에 작은 노드부터 방문한다면 오름차순으로, 큰 노드부터 방문한다면 내림차순으로 정렬한다.

 

기존 dfs의 탐색 방문을 boolean타입의 visit을 사용했다면 각 노드의 방문 순서를 체크하기 위해 int타입으로 바꾸어 0이면 방문하지 않았고 방문했다면 정수형태 1~*의 값으로 저장되게끔 한다.

 

코드 - 24479 깊이 우선 탐색 1

package 백준;

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

public class b24479 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] visit;
    static int order = 1;
    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());

        // init()
        visit = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph.get(from).add(to);
            graph.get(to).add(from);
        }

        // graph의 자식 노드를 오름차순으로 정렬
        for (int i = 1; i < n+1; i++) {
            graph.get(i).sort(Comparator.naturalOrder());
        }

        dfs(r);

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

    static void dfs(int idx) {
        visit[idx] = order++;

        for (int i = 0; i < graph.get(idx).size(); i++) {
            int adj = graph.get(idx).get(i);
            // 방문하지 않았다면
            if (visit[adj] == 0) {
                dfs(adj);
            }
        }
    }
}

코드 - 24479 깊이 우선 탐색 2

// graph의 자식 노드를 오름차순으로 정렬
for (int i = 1; i < n+1; i++) {
    graph.get(i).sort(Comparator.reverseOrder());
}

위 코드의 정렬부분 내림차순이 되도록 다음과 같이 수정해주면 된다.