b24497. 알고리즘 수업 - 깊이 우선 탐색 1

 

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

 

 

 

이 문제는 그래프 탐색 알고리즘인 DFS(Depth First Search)를 활용하여

특정 시작 정점에서 탐색을 수행하며, 각 정점을 방문한 순서를 기록하는 문제다.

아래 코드는 문제를 해결하기 위한 전체적인 흐름과 구현 방식을 포함하고 있다.
우선, 입력으로는 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점 R이 주어진다.

이 정보를 기반으로 그래프를 인접 리스트 형태로 표현하기 위해 list라는 배열을 생성한다.

이 배열은 각 정점이 연결된 다른 정점들을 저장하는 리스트를 담고 있다.

이를 통해 그래프를 효율적으로 관리하고 탐색을 수행할 수 있다.

입력으로 주어진 간선을 처리하여 무방향 그래프를 구성한다.

각 정점의 연결 정보를 정렬하여 탐색 시 오름차순으로 방문할 수 있도록 준비한다.

이렇게 정렬된 그래프는 문제의 조건을 만족하기 위해 필요하다.

깊이 우선 탐색(DFS)을 수행하기 위해 재귀 함수 DFS를 작성한다.

이 함수는 탐색을 시작하는 정점을 입력받아,

방문 순서를 기록하는 배열 ans에 현재 카운트를 저장한다.

이후 해당 정점에 연결된 모든 정점을 탐색하며,

아직 방문하지 않은 정점에 대해 재귀적으로 DFS를 호출한다.

방문 순서는 count라는 전역 변수로 관리하여, 탐색 순서를 차례로 기록된다.

마지막으로, 각 정점의 방문 순서를 출력한다.

 

 

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

    static int N, M, R;
    static int[] ans;
    static ArrayList<Integer>[] list;
    static int count;

    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];
        ans = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 1; 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]);
        }

        count = 1; // 초기값 설정
        DFS(R);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }
        System.out.println(sb);
    }

    static void DFS(int r) {
        ans[r] = count++;
        for (int next : list[r]) {
            if (ans[next] == 0) { // 방문하지 않은 정점인 경우
                DFS(next);
            }
        }
    }
}