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

 

 

 

문제 링크

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

프로그래머스

 

 

 

문제

1. 1부터 n까지 n개의 노드가 있는 그래프에서 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하라.
2. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다.

3. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수가 주어진다.

4. 노드의 개수 n은 2 이상 20,000 이하이다.
5. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있다.

 

 

문제 풀이

1. 최단 경로를 체크하는 문제로 BFS 알고리즘을 이용하여 구할 수 있다. 

2. 이미 방문한 노드는 최단 경로로 이미 방문한 노드이기 때문에 다시 방문하지 않는다.

 

 

코드 1

while문을 한번 수행할 때마다 기준 node에서 연결된 간선을 통해 다음 node를 담는다.

가장 멀리 떨어진 노드의 개수를 구하는 문제로 while문에서 queue.poll()을 바로 수행하지 않고 queue의 size를 체크하여 새로 추가된 node를 꺼내지 않도록 하고, 마지막 size 값이 가장 멀리 떨어진 노드의 개수가 된다.

import java.util.Queue;
import java.util.LinkedList;
class Solution {
    public int solution(int n, int[][] edge) {
        Queue<Integer> queue = new LinkedList();
        queue.offer(1);
        int [] visited = new int [n+1];
        visited[1] = 1; 

        int cnt =0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                int cur = queue.poll();
                for(int [] e: edge){
                    if(e[0] == cur && visited[e[1]] != 1) {
                        queue.offer(e[1]);
                        visited[e[1]] = 1;
                    } else if(e[1] == cur && visited[e[0]] != 1){
                        queue.offer(e[0]);
                        visited[e[0]] = 1;
                    }
                }
            }
            cnt = size;
        }
        return cnt;
    }
}

 

실행 결과 1

 

 

 

---

 

코드 1의 방법이 실행 속도가 느린 것 같아. 좀 더 개선해 보기로 했다. 

 

 

코드 2

HashMap과 HashSet을 이용하여 edge에 대한 정보를 미리 담아둔다. 이렇게 수정하면 while문에서 다음 node를 찾을 때 성능이 향상될 수 있다. 또한, 다음 노드로 이동한 후 이미 방문한 노드는 더 이상 방문하지 않을 것 임으로 Map에서 삭제한다.

import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int n, int[][] edge) {
        
        Map<Integer,Set<Integer>> vertexMap = new HashMap();
        for(int[] e : edge){
            for(int i=0; i<2; i++){
                Set<Integer> set = vertexMap.getOrDefault(e[i],new HashSet());
                set.add(e[(i+1)%2]);
                vertexMap.put(e[i],set);
            }
        }
        
        Queue<Integer> queue = new LinkedList();
        queue.offer(1);
        int [] visited = new int [n+1];
        visited[1] = 1; 

        int cnt =0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                int cur = queue.poll();
                if(!vertexMap.containsKey(cur)) continue;
                
                Set<Integer> set =  vertexMap.get(cur);
                for(int next:set){
                    if(visited[next] == 1) continue;
                    queue.offer(next);
                    visited[next] = 1; 
                } 
                vertexMap.remove(cur);
            }
            cnt = size;
        }
        return cnt;
    }
}

 

 

실행 결과 2