[백준] 24445 알고리즘 수업 - 너비 우선 탐색 2 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색)  를 활용합니다.

 

이 문제는 24444 번 문제와 거의 같습니다만, 다른 점은 내림차순으로 조회한다는 점입니다.

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

Collections.sort에 Collections.reverseOrder를 추가해서 내림차순으로 정렬시킵니다.

그러면 자동으로 내림차순 순서로 방문하게 되겠지요.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, R;
//	static int answer = 0;
	static int[] answer;
	static ArrayList<Integer>[] arr = new ArrayList[100001];
	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());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		answer = new int[N];
		for(int i=0;i<100001; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr[u].add(v);
			arr[v].add(u);
		}
		
		for(int i=0;i<N;i++) {
			Collections.sort(arr[i], Collections.reverseOrder());
		}
		
		BFS(R - 1);
		for(int i=0;i<N;i++) {
			System.out.println(answer[i]);
		}
	}
	
	static void BFS(int now) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(now);
		boolean[] visited = new boolean[N];
		visited[now] = true;
		
		int rank = 1;
		while(!q.isEmpty()) {
			int temp = q.poll();
			answer[temp] = rank++;
			for(int next = 0; next < arr[temp].size(); next++) {
				int nextNode = arr[temp].get(next);
				if(visited[nextNode] == true) continue;
				visited[nextNode] = true;
				q.offer(nextNode);
			}
		}
	}
}