b24480. 알고리즘 수업 - 깊이 우선 탐색 2

 

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

 

 

 

📌 자바(Java)로 푸는 깊이 우선 탐색(DFS) - 백준 24480 문제 풀이 🚀

---

🔎 문제 개요

이 문제는 백준 24480번 - 깊이 우선 탐색 2 문제입니다.
주어진 그래프를 깊이 우선 탐색(DFS)하며 방문 순서를 기록해야 합니다.
단, 내림차순(큰 숫자부터) 으로 방문해야 한다는 점이 특징입니다.

---

💡 예제 입력

5 5 1
1 4
1 2
2 3
2 4
3 4

💡 예제 출력

1
4
3
2
0

➡ 1번 정점부터 내림차순으로 DFS 탐색하며 방문 순서를 출력해야 합니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 DFS(깊이 우선 탐색) + 정렬을 활용합니다.

✏️ 주요 고려 사항

✔ DFS를 사용하여 그래프를 탐색
✔ 간선 정보를 저장할 때 내림차순으로 정렬
✔ 정점 방문 순서를 isVisited[] 배열에 기록

---

🔹 Java 코드 해설

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 b24480 {

    static int N, M, R, count = 1; // 정점 수, 간선 수, 시작 정점, 방문 순서 카운트
    static ArrayList<Integer>[] list; // 인접 리스트
    static int[] isVisited; // 방문 순서 저장 배열

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

        // 입력 처리
        N = sToInt(st.nextToken()); // 정점 개수
        M = sToInt(st.nextToken()); // 간선 개수
        R = sToInt(st.nextToken()); // 시작 정점

        isVisited = new int[N + 1]; // 방문 순서 저장 배열
        list = new ArrayList[N + 1];

        // 인접 리스트 초기화
        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = sToInt(st.nextToken());
            int b = sToInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        // 내림차순 정렬 (큰 숫자부터 탐색)
        for (int i = 1; i <= N; i++) {
            list[i].sort(Collections.reverseOrder());
        }

        // DFS 실행
        DFS(R);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(isVisited[i]).append("\n");
        }
        System.out.println(sb);
    }

    // 문자열 -> 정수 변환 함수
    static int sToInt(String s) {
        return Integer.parseInt(s);
    }

    // 깊이 우선 탐색 (DFS)
    static void DFS(int start) {
        isVisited[start] = count++; // 방문 순서 기록

        for (int next : list[start]) { // 연결된 정점 순회
            if (isVisited[next] == 0) { // 방문하지 않은 경우
                DFS(next);
            }
        }
    }
}

---

🔍 코드 설명

📌 1. 입력 처리 및 그래프 초기화

N = sToInt(st.nextToken()); // 정점 개수
M = sToInt(st.nextToken()); // 간선 개수
R = sToInt(st.nextToken()); // 시작 정점

isVisited = new int[N + 1]; // 방문 순서 저장 배열
list = new ArrayList[N + 1];

// 인접 리스트 초기화
for (int i = 0; i <= N; i++) {
    list[i] = new ArrayList<>();
}

• 정점 개수(N), 간선 개수(M), 시작 정점(R) 을 입력받음
• isVisited[] 배열을 사용하여 방문 순서를 기록
• list[] 배열을 사용하여 인접 리스트를 저장

---

📌 2. 간선 정보 입력 및 내림차순 정렬

// 간선 정보 입력
for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = sToInt(st.nextToken());
    int b = sToInt(st.nextToken());
    list[a].add(b);
    list[b].add(a);
}

// 내림차순 정렬 (큰 숫자부터 탐색)
for (int i = 1; i <= N; i++) {
    list[i].sort(Collections.reverseOrder());
}

• ArrayList[]를 사용하여 인접 리스트 방식으로 간선 정보를 저장
• 정점 번호가 큰 순서대로 방문하기 위해 Collections.reverseOrder()로 정렬

---

📌 3. DFS 탐색

// DFS 실행
DFS(R);

• 시작 정점(R)부터 DFS 탐색을 시작

---

📌 4. DFS 탐색 구현

static void DFS(int start) {
    isVisited[start] = count++; // 방문 순서 기록

    for (int next : list[start]) { // 연결된 정점 순회
        if (isVisited[next] == 0) { // 방문하지 않은 경우
            DFS(next);
        }
    }
}

• DFS를 실행하면서 방문 순서를 기록
• 연결된 정점 중 방문하지 않은 정점들을 순서대로 방문
• 이미 방문한 정점은 다시 방문하지 않음

---

🔥 시간 복잡도 분석

연산	최악의 경우 수행 횟수 시간 복잡도	시간 복잡도
간선 입력 및 정렬	M log M	O(M log M)
DFS 탐색	N + M	O(N + M)
총합		O(N + M log M)

✅ 빠른 DFS 탐색이 가능하며, 그래프의 크기가 크더라도 효율적

---

🏆 정리

✅ 핵심 포인트

✔ DFS를 사용하여 그래프를 탐색하며 방문 순서를 기록
✔ 정점이 큰 숫자부터 방문해야 하므로 내림차순 정렬
✔ 방문 순서는 isVisited[] 배열을 사용하여 저장

---

🎯 이 알고리즘의 장점

✅ DFS를 활용하여 빠르게 탐색 가능
✅ 인접 리스트 + 정렬을 통해 정점 방문 순서 제어 가능
✅ O(N + M log M) 시간 복잡도로 효율적인 탐색 가능

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!
궁금한 점은 댓글로 남겨주세요! 😊