99클럽 코테 스터디 5일차 TIL (미들러): [백준][Java] 24444 알고리즘 수업 - 너비 우선 탐색 1 - 실버2

 

문제 보기

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

 

 

풀이

 

어제 문제의 BFS 버전이라 역대급 속도로 풀었다.

 

  private static void bfs(List<Integer>[] arr, int r, int[] order) {
    boolean[] visited = new boolean[arr.length + 1];
    Queue<Integer> queue = new LinkedList<>();
    visited[r] = true;
    queue.add(r);
    while (!queue.isEmpty()) {
      int cur = queue.poll();
      order[cur] = count++;
      for(int i : arr[cur]) {
        if (!visited[i]) {
          visited[i] = true;
          queue.add(i);
        }
      }
    }
  }

기본 BFS 문제다.

큐에서 원소를 꺼낼 때 순서를 체크하였다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
  private static int count = 1;
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");
    int N = Integer.parseInt(inputs[0]);
    int M = Integer.parseInt(inputs[1]);
    int R = Integer.parseInt(inputs[2]);

    List<Integer>[] arr = new ArrayList[N + 1];
    for(int i = 1; i <= N; i++) {
      arr[i] = new ArrayList<>();
    }
    while (M-- > 0) {
      inputs = br.readLine().split(" ");

      arr[Integer.parseInt(inputs[0])].add(Integer.parseInt(inputs[1]));
      arr[Integer.parseInt(inputs[1])].add(Integer.parseInt(inputs[0]));
    }
    for(int i = 1; i <= N; i++) {
      arr[i].sort(Comparator.naturalOrder());
    }

    int[] order = new int[N + 1];
    bfs(arr, R, order);
    for(int i = 1; i <= N; i++) {
      bw.write(order[i] + "\n");
    }

    bw.flush();
    bw.close();

  }

  private static void bfs(List<Integer>[] arr, int r, int[] order) {
    boolean[] visited = new boolean[arr.length + 1];
    Queue<Integer> queue = new LinkedList<>();
    visited[r] = true;
    queue.add(r);
    while (!queue.isEmpty()) {
      int cur = queue.poll();
      order[cur] = count++;
      for(int i : arr[cur]) {
        if (!visited[i]) {
          visited[i] = true;
          queue.add(i);
        }
      }
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/24444.%E2%80%85%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%E2%80%85%EC%88%98%EC%97%85%E2%80%85%EF%BC%8D%E2%80%85%EB%84%88%EB%B9%84%E2%80%85%EC%9A%B0%EC%84%A0%E2%80%85%ED%83%90%EC%83%89%E2%80%851

CodingTest_AutoSave/백준/Silver/24444. 알고리즘 수업 － 너비 우선 탐색 1 at main · MetroDefro/Codi