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

풀이 방법

-변수

• 간선으로 연결된 노드들을 담는 Set list
• list에 포함된 노드와 연결된 노드들을 저장하는 Set temp
• 아직 list에 들어가지 않은 노드의 수 left
• 새롭게 추가될 노드 수 count (=temp.size())

1. list에 1을 넣는다

2. 1과 연결된 노드들을 temp에 넣는다

바로 list에 넣지 않는 이유는.. 반복문에서 이 친구들을 포함해서 또 노드를 추가하고 추가해서.. 따로 만들어버렸다

그리고 Set인 이유는.. 중복으로 포함될 수 있기 때문이다.

3. 새로 추가된 노드들을 list로 옮겨준다

list.addAll(temp) 메서드를 이용했다

4. temp를 클리어 해준다.

5. 1~4 과정을 반복하되 left==0이면, 즉 모든 간선들이 list 배열에 추가됐을 때 마지막으로 센 count를 return 한다.

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {        
        Set<Integer> list=new HashSet<>(); //가장 거리가 먼 간선이 아닌것;
        Set<Integer> temp=new HashSet<>();
        int left=n-1;	//남은 노드 수, 1제외
        int count=0; 	// 새로 큐에 포함될 노드의 개수
        
        list.add(1);
        
        while(true) {
        	for(int i=0;i<edge.length;i++) {
        		if(!list.contains(edge[i][0])&& list.contains(edge[i][1])){
        			temp.add(edge[i][0]);
        		}
        		if(!list.contains(edge[i][1])&& list.contains(edge[i][0])){
        			temp.add(edge[i][1]);
        		} 
        	}
        	//temp를 list에 추가
        	count=temp.size();
        	list.addAll(temp);
        	temp.clear();
        	left -= count;
        	if(left==0) {
        		return count;
        	}
        }
        
    }
}

코드 실행했을 때 러닝타임이 긴 편이었는데.. 그래도 통과

아마도 for문을 도는 과정에서 불필요한 비교를 중첩적으로 해줘서 그런 것 같다..

그래도.. 다른 사람들 코드랑 비교해봤을 때 짧고,, 독특한 접근 방식이라 만족..