[swexpert] 1238. Contact (java, bfs)

hashSet은 중복되는 값이 들어온다고 해서 없애주기 위해 사용했다. 

링크드 리스트를 배열과 조합하여 시작하는 숫자들(부모 노드들)은 배열에 넣고 

해당 숫자에서 뻗어나가는 자식들은 노드리스트에 넣었다. 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	static int n;
	static int start,tc;
	static LinkedList<Integer>[] list;
	static int answer,total_cnt;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			n=sc.nextInt();
			start=sc.nextInt();
			answer=0;
			total_cnt=0;
			list=new LinkedList[101];
			for (int i = 0; i < 101; i++) {
				list[i]=new LinkedList<Integer>();
			}
			Set<Integer[]> s=new HashSet<>();
			for (int i = 0; i < n/2; i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				if(!s.contains(new Integer[] {from,to})) {
					s.add(new Integer[] {from,to});
				}
			}
			
			for(Integer[] e:s) {
				list[e[0]].add(e[1]);
			}
			bfs();
			System.out.printf("#%d %d\n",++tc,answer);
		}
	}
	private static void bfs() {
		Queue<Integer[]> q=new LinkedList<>();
		q.add(new Integer[] {start,0});
		boolean[] vis=new boolean[101];
		vis[start]=true;
		while(q.size()!=0) {
			int cur=q.peek()[0];
			int cnt=q.peek()[1];
			q.poll();
			int max=0;
//			System.out.println("cur:"+cur);
			for (int i = 0; i < list[cur].size(); i++) {
				int next=list[cur].get(i);
				if(vis[next])continue;
//				System.out.println("next:"+next);
				vis[next]=true;
                if(cnt>total_cnt){
                 	   answer=next;
                    total_cnt=cnt;
                }else if(cnt==total_cnt && next>answer){
                    answer=next;
                }
				q.add(new Integer[] {next,cnt+1});

			}
			if(max!=0)
			answer=max;
			
		}
		
	}
}