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

문제 : boj24445

 

    bfs가 뭔지 모른다면 이 글을 참고해보자. 일반적인 bfs 구현인데, 문제는 다음 정점을 내림차순으로 선택해야 한다. 그리고 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 된다.

 

  그러니 인접 리스트로 간선을 표현하자. 이 때 내림차순으로 다음 정점을 선택해야 하므로, 미리 내림차순으로 각 정점의 간선들을 정렬시켜두면 된다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    int[] answer;
    ArrayList<Integer>[] edges;
    int idx = 0;
    int[] v;

    private void solution() throws Exception {
        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());
        edges = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        answer = new int[n + 1];
        v = new int[n + 1];
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edges[u].add(v);
            edges[v].add(u);
        }
        for (int i = 1; i <= n; i++) Collections.sort(edges[i], Collections.reverseOrder());

        Queue<Integer> q = new ArrayDeque<>();
        q.add(r);
        int visitCnt = 1;
        v[r] = visitCnt;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : edges[cur]) {
                if (v[next] != 0) continue;
                v[next] = ++visitCnt;
                q.add(next);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(v[i]).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}