JAVA 백준 24445 알고리즘 수업 - 너비 우선 탐색 2 (그래프)

 

 

---

문제

1. 첫째 줄에 정점 개수 N ( 5 <= N <= 100000), 간선의 수 M ( 1 <= M <= 200000), 시작 정점 ( 1 <= R <= N) 이 주어진다.
2. 둘째 줄부터 M개의 줄에 간선의 정보 u v ( 1 <= u < v <= N, u != v) 가중치 1인 양방향 간선이 주어진다.
3. 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력하는데 i번쨰 줄에 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서를 1로 시작하며, 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
4. 방문 순서는 내림차순으로 방문하도록 한다.

---

 

최종 코드

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

public class Main {
    public static int[] visited;
    public static ArrayList<Integer>[] list;
    public static int count = 1;

    public static void bfs(int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        visited[s] = count++;

        while (!queue.isEmpty()) {
            int num = queue.poll();
            for (int i = 0; i < list[num].size(); i++) {
                if (visited[list[num].get(i)] == 0) {
                    queue.offer(list[num].get(i));
                    visited[list[num].get(i)] = count++;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        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());

        visited = new int[N + 1];
        list = new ArrayList[N + 1];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            list[u].add(v);
            list[v].add(u);
        }

        for (int i = 1; i < N + 1; i++) {
            Collections.sort(list[i], Collections.reverseOrder());
        }

        bfs(R);

        for (int i = 1; i < N + 1; i++) {
            System.out.println(visited[i]);
        }
    }
}

 

 

24480번의 dfs를 bfs로만 바꾸면 된다.

 

https://gamja00.tistory.com/150

JAVA 백준 24480 알고리즘 수업 - 깊이 우선 탐색 2 (그래프)