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

문제 : 프로그래머스 - 가장 먼 노드

카테고리 : 그래프

출처 : 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

✏️ 내 풀이

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 이런 식으로 그래프의 각 노드와 노드 간의 간선 정보가 주어지는데, 이를 통해 노드 1로부터 가장 멀리떨어진 노드들을 찾아야하는 문제였다.

"가장 멀리 떨어진" 노드들을 판단하기 위해서는, 노드 1과 나머지 노드들간의 거리를 다 구해서 비교해야 겠다는 생각이 들었다.

각 노드들간의 거리를 구하려면, 노드들이 서로 어디까지 연결되어있는지 다 탐색해봐야 한다고 생각해서, BFS 방식을 사용했다.

0. BFS를 위한 Queue 자료구조 직접 구현

1. 인접 리스트 방식으로 그래프 구현

const graph = Array.from( // 인접 리스트 방식으로 그래프 구현
        Array(n+1), // 1~n 까지 사용할 것이므로
        () => []
);

for(let [i,j] of edge){ // 그래프 초기화 
    graph[i].push(j);
    graph[j].push(i);
}

2. BFS로 그래프 탐색

let dist = new Array(n+1).fill(-1); // 1번 노드와 1 ~ n번 노드 사이의 거리  
let queue = new Queue();

dist[1] = 0; 
let max_dist = 0; // 1번 노드와 1 ~ n번 노드 사이의 거리 중 최댓값

queue.enqueue([1, 0]); // 1번 노드로부터 탐색 시작 

while(queue.size()){
    let [node, now_dist] = queue.dequeue(); // [1, 0]
    
    for(let x of graph[node]){ // 2, 3
        if(dist[x] !== -1) continue;// 방문 전 && 거리가 업데이트 될 수 있을 때 
        
        dist[x] = now_dist+1; // 방문 표시

        if(max_dist < now_dist+1){ 
            max_dist = now_dist+1;
        }

        queue.enqueue([x, now_dist+1]);
    }
}

• 한 번 방문했으면, 그 다음 방문에는 탐색하면서 1번 노드와의 거리가 더 증가했을 것이니, 최단거리라 업데이트 될 상황은 없을 것이다. 따라서, 처음 방문인 노드만 Queue에 넣어주면서 탐색한다.
• 나중에 1번 노드와 제일 멀리 떨어져 있는 노드의 수를 구해야 하므로, 1번 노드와 1 ~ n번 노드 사이의 거리 중 최댓값을 나타내는 변수 max_dist를 선언해주고, 각 node들을 방문할 때마다 업데이트 가능 시 업데이트 해준다.

3. 가장 멀리 떨어진 노드들의 개수 계산

let answer = 0;
dist.forEach((dist) => {
    if(dist === max_dist)
        answer++;
})

return answer;

---

✒️ Solution

배열로 큐를 사용할 때 shift 연산은 O(n)이므로 우리가 생각하는 queue와는 다르게 동작한다고 했는데, 만약 요소가 적을 경우에는 자바스크립트 엔진에서 어느정도 최적화를 해준다.

=> 따라서, 이 문제에서는 배열의 shift를 이용해서 queue를 사용해도 괜찮다 !

Solution을 보고, 내 코드를 개선해보았다.

for(let [i,j] of edge)  =>  for(const[src, dest] of edge)

나는 BFS를 돌면서 queue에 [node 번호, 거리] 를 넘겨줬는데, 거리 값을 넘겨주지 않고 그냥 각 노드를 queue에 넣을 때 따로 distance를 계산해줄 수 있다.

distance[현재 노드] = distane[이전 노드] + 1

나는 max_dist 변수를 따로뒀지만 하위 방식으로 더 짧고 간단하게 구할 수 있다 !

const max = Math.max(...distance);
return distance.filter(item => item === max).length;