[Java] 백준(실버-2) 24479번 - 알고리즘 수업(깊이 우선 탐색 1)

문제 분석

---

작성코드

---

import java.io.*;
import java.util.*;

class Main {
    // 방문한 정점을 담을 배열
    public static int[] visited;
    // 인접 리스트
    public static List<List<Integer>> list;
    // 방문 순서
    public static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        // 방문 배열 초기화
        visited = new int[N+1];

        // 인접리스트 초기화(1 ~ N)
        list = new ArrayList<>();
        for(int i=1; i<=N+1; i++) {
            list.add(new ArrayList<Integer>());
        }

        // M개의 간선 입력받으며 인접리스트 구현
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 무방향이기에 양쪽 정점을 모두 추가
            list.get(start).add(end);
            list.get(end).add(start);
        }

        // 인접리스트의 각 노드 오름차순 정렬
        for(int i=0; i<list.size(); i++) {
            Collections.sort(list.get(i));
        }
        
        // 방문 순서 초기화
        cnt = 1;
        
        // DFS 호출
        DFS(R);

        for(int i=1; i<visited.length; i++) {
            bw.write(visited[i]+"\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int node) {
        visited[node] = cnt;
        for(int n : list.get(node)) {
            if(visited[n] == 0) {
                cnt++;
                DFS(n);
            }
        }
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.