구름톤 챌린지 14일차

문제

https://level.goorm.io/exam/195696/%EC%9E%91%EC%9D%80-%EB%85%B8%EB%93%9C/quiz/1

구름LEVEL

 

코드

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

class Main {
	static LinkedList<Integer> list [];
	static int count = 0;
	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 k = Integer.parseInt(st.nextToken());
		
		list = new LinkedList[n+1];
		for(int i=1;i<=n;i++){
			list [i] = new LinkedList<Integer>();
		}
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			list[s].add(e);
			list[e].add(s);
		}
		
		for(int i=1;i<=n;i++){
			Collections.sort(list[i]);
		}
		
		int end = bfs(n, k);
		System.out.print(count+" "+end);

	}
	
	static int bfs(int n, int k){
		boolean visited [] = new boolean [n+1];
		Queue<Integer> que = new LinkedList<>();
		
		que.add(k);
		visited[k] = true;
		
		int end = 0;
		while(!que.isEmpty()){
			int val = que.poll();
			count ++;
			end = val;
			
			for(int i=0;i<list[val].size();i++){
				if(visited[list[val].get(i)]) continue;
				
				que.add(list[val].get(i));
				visited[list[val].get(i)] = true;
				break;
			}
		}
		
		return end;
	}
}