백준 24445 자바

 

24444번에서 정렬만 내림차순으로 바꿔주면 되는 문제입니다.

자세한 풀이는 24444번 풀이를 봐주세요!

 

import java.util.*;
import java.io.*;
public class Main {

    static int N;
    static ArrayList<Integer>[] list; // 노드 그래프 표현

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1]; // 편의를 위해 1번부터 시작하므로 N+1 크기

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
        // 이 부분 안 하면 NullPointerException 발생합니다.

        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);
        }
        // 위에 말한 대로 1-2면 2-1도 되는 거니까 양쪽으로 넣어줍니다.

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

        bfs(R);
    }
    private static void bfs(int x) {
        Queue<Integer> queue=new LinkedList<>();
        queue.add(x);

        boolean []visited=new boolean[N+1];
        visited[x]=true;

        int cnt=0;
       
        int[] order=new int[N+1];
     
        while(!queue.isEmpty()) {
            
                int q=queue.poll();
                cnt++;
                order[q] = cnt;
                for(int i:list[q]) {
                    if(!visited[i]) {
                        visited[i]=true;
                        queue.add(i);
                    }
            }
        }
       
        for(int i=1;i<=N;i++) {
            System.out.println(order[i]);
        }
    }
}