6118_숨바꼭질

사용 알고리즘: bfs

사용 언어: java

 

package ssafyRoom2;

import java.util.*;

public class Main_bj_6118_숨바꼭질 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //노드 개수
		int m = sc.nextInt();
		
		List<Integer>[] list = new ArrayList[n+1];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			list[a].add(b);
			list[b].add(a);
		}
		
		boolean[] visit = new boolean[n+1];
		visit[1] = true;
		
		int[] len = new int[n+1];
		
		bfs_6118(list, visit, len);
		
		int max = 0;
		int num = 0;
		int sameCnt = 0;
		
		for(int i=1; i<n+1; i++) {
			if(max < len[i]) {
				max = len[i];
				num = i;
				sameCnt = 1;
			} else if(max == len[i]) {
				sameCnt++;
			}
		}
		
		System.out.println(num+" "+max+" "+sameCnt);
	}

	private static void bfs_6118(List<Integer>[] list, boolean[] visit, int[] len) {
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {1, 0});
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			len[p[0]] = p[1];
			
			for(int nxt : list[p[0]]) {
				if(!visit[nxt]) {
					visit[nxt] = true;
					q.add(new int[] {nxt, p[1]+1});
				}
			}
		}
	}

}

 

 

어렵지 않게 풀 수 있는 문제다. bfs 연습하기 좋은 듯하다.