구름톤 챌린지 19일차

문제

https://level.goorm.io/exam/195701/%EB%8C%80%EC%B2%B4-%EA%B2%BD%EB%A1%9C/quiz/1

구름LEVEL

 

코드

import java.io.*;
import java.util.*;

class Main {
	static LinkedList<Integer> arr [];
	public static void main(String[] args) 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 s = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		arr = new LinkedList[n+1];
		
		for(int i=1;i<=n;i++){
			arr[i] = new LinkedList<>();
		}
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
		
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			arr[u].add(v);
			arr[v].add(u);
		}
		
		for(int i=1;i<=n;i++){
			if(i == s || i == e) {
				System.out.println("-1");
			}
			else{
				int count = bfs(n, s, e, i);
				System.out.println(count);
			}
			
		}
		
	}
	
	static int bfs(int n, int s, int e, int block){
		int visited [] = new int [n+1];
		
		Arrays.fill(visited, Integer.MAX_VALUE);
		
		Queue<Integer> que = new LinkedList<>();
		que.add(s);
		visited[s] = 1;
		
		while(!que.isEmpty()){
			int curr = que.poll();
			if(curr == e){
				return visited[curr];
			}
			
			for(int next : arr[curr]){
				if(next == block) continue;
				if(visited[next] > visited[curr] + 1) {
					que.add(next);
					visited[next] = visited[curr] + 1;
				}
			}
		}
		
		
		return -1;
		
	}
}