[백준 24445/자바(java)] 알고리즘 수업 - 너비 우선 탐색 2

문제

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

백준(baekjoon) 24445 알고리즘 수업 - 너비 우선 탐색 2

문제 분석

그래프와 정렬, bfs를 이용하여 너비 우선 탐색을 하는 문제이다.

- BufferedReader, BufferedWriter, StringTokenizer을 사용하여 입출력을 좀 더 효율적으로 구현

- Collections.sort()와 reverseOrder()를 이용하여 내림차순 정렬

- 재귀 BFS를 이용하여 너비 우선 탐색을 해결

 

정답 코드

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

public class Main {
    static int vertex, edge, startVertex, count = 1; //정점, 간선, 시작 정점, 개수
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); //그래프 값 저장
    static int[] result; //순번 저장 배열
    static boolean[] visited; //방문 확인 배열

    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()); //그래프 값 저장

        vertex      = Integer.parseInt(st.nextToken());
        edge        = Integer.parseInt(st.nextToken());
        startVertex = Integer.parseInt(st.nextToken());

        result  = new int[vertex + 1];
        visited = new boolean[vertex + 1];

        for (int i = 0 ; i <= vertex ; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0 ; i < edge ; i++) {
            st = new StringTokenizer(br.readLine());
            int fromVertex = Integer.parseInt(st.nextToken());
            int toVertex = Integer.parseInt(st.nextToken());
            // 무방향이기 때문에 양쪽으로 정보를 추가
            graph.get(fromVertex)
                 .add(toVertex);
            graph.get(toVertex)
                 .add(fromVertex);
        }

        //너비 우선 탐색 수행
        bfs(startVertex);

        for (int i = 1 ; i <= vertex ; i++) {
            bw.write(result[i] + "\n");
        }
        bw.flush(); //결과 출력
        bw.close();
        br.close();
    }

    private static void bfs(int vertex) {
        Queue<Integer> queue = new LinkedList<Integer>();
        result[vertex]  = count++; //순번 저장
        visited[vertex] = true; //방문 확인
        queue.add(vertex);
        while (!queue.isEmpty()) {
            int point = queue.poll();
            Collections.sort(graph.get(point), Collections.reverseOrder());
            for (int next : graph.get(point)) { //인접 정점 탐색
                if (!visited[next]) { //방문했는지 확인
                    visited[next] = true; //방문 확인
                    result[next]  = count++; //순번 확인
                    queue.add(next);
                }
            }
        }
    }
}