[프로그래머스] 가장 먼 노드 -Java

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
		int answer;
	    public int solution(int n, int[][] edge) {
	    	answer=0;
	        List<Integer> list[]=new List[n+1];
	        for(int i=0; i<=n; i++) list[i]=new ArrayList<>();
	        
	        for(int i=0; i<edge.length; i++) {
	        		list[edge[i][0]].add(edge[i][1]);
	        		list[edge[i][1]].add(edge[i][0]);
	        }
	        
	        boolean [] visited= new boolean[n+1];
	        bfs(list,visited);
	        return answer;
	    }

		private void bfs(List<Integer>[] list, boolean[] visited) {
			Queue<Integer> queue=new LinkedList<Integer>();
			visited[1]=true;
			queue.offer(1);
			
			while(true) {
				int size=queue.size();
				if(size==0) return;
				answer=0;
				for(int i=0; i<size; i++) {
					int vertex=queue.poll();
					answer++;
					
					for(int j=0; j<list[vertex].size(); j++) {
						int end=list[vertex].get(j);
						if(!visited[end]) {
							queue.offer(end);
							visited[end]=true;
						}
					}
				}
				
			}
			
		}
	}

소요시간 : 20분

 

전형적인 BFS문제였습니다.

 

각 간선의 연결정보를 저장하기 위해 LIST를 2차원배열로 선언하였습니다.

 

양방향이기 때문에 1-3 이면 1->3, 3->1 을 모두 저장해주었습니다.

 

그리고 그 다음에는 그냥 BFS돌렸습니다..

 

Level 3문제 치고는 엄청엄청 쉬운편이라고 생각합니다!!