[그래프] 가장 먼 노드 - Java코드 ★★★

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

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

 

 

문제

 

 

설계

그래프 탐색은 이미 bfs, dfs 파트에서 하였다.

이문제는 1에서 시작해서 넓이 level을 중심으로 단계적 탐색이 이루어져야 하므로 bfs문제로 보았다.

1로 부터 단계적으로 넓이중심에 탐색을 진행하면서,  반복적으로 진행해야하므로 

Queue를 이용해서 1을 기준으로 단계별로 저 add, poll를 반복해준다

여기서 순회한 간선에 대해서는 배열 flag를 이용하거나, set을 이용해주면 되는데, 나는 set 자료구조를 이용했다.

 

풀이

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
    public int solution(int n, int[][] edge) {
        HashSet<Integer> set = new HashSet<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        set.add(1);
        int cnt=1;
        while(!q.isEmpty()) {
        	cnt=q.size();
        	for(int i=0;i<cnt;i++) {
        	    int peek=q.poll();
        	    for(int j=0;j<edge.length;j++) {
        	        if(edge[j][0]==peek && !set.contains(edge[j][1])) {
        	            set.add(edge[j][1]);
        	            q.add(edge[j][1]);  
        	        }
        	        if(edge[j][1]==peek && !set.contains(edge[j][0])) {
        	            set.add(edge[j][0]);
        	            q.add(edge[j][0]);  
        	        }
        	    }
        	}
        }    
        return cnt;
    }
}

 

 

테스트 케이스

6, {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}}, 3
11, {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 8}, {4, 9}, {5, 9}, {5, 10}, {6, 10}, {6, 11}}, 4
4, {{1, 2}, {2, 3}, {3, 4}}, 1
2, {{1, 2}}, 1
5, {{4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}}, 2
4, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}, 1
4, {{1, 4}, {1, 3}, {2, 3}, {2, 1}}, 3
4, {{3, 4}, {1, 3}, {2, 3}, {2, 1}}, 1
4, {{4, 3}, {1, 3}, {2, 3}}, 2