프로그래머스 데브코스 - [3단계] 가장 먼 노드

 

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

입출력 예

ㄹㅇㄴㅁ

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

주어진 문제에서 핵심 키워드는 "노드", "간선", "최단 경로" 이다

우선 인접 리스트로 그래프를 표현한다 단, 간선이 1부터 6이기 때문에 편의상 배열의 길이는 n + 1로 만들어둔 후 인접리스트이기 때문에 초기값으로 빈 배열을 둔다

그리고 입력값으로 주어진 간선 배열을 순회하면서 인접리스트를 채워준다

노드1부터의 각 노드까지의 거리를 나타낸 배열도 선언해준다 이 때, 노드 1번은 이미 방문한 상태이기 때문에 초기값으로 1을 주고 나머지는 모두 0으로 채운다

각 노드까지의 거리는 최단 거리로 채워야 하기 때문에 BFS(너비 우선 탐색)를 사용한다. BFS는 Queue를 이용하므로 Queue를 구현해준다

이후 큐에 노드1부터 넣고 각 노드별 목적지를 구해준다

// 큐 구현
class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(value) {
        this.queue[this.rear++] = value;
    }
    
    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value;
    }
    
    isEmpty() {
        return this.rear === this.front;
    }
}

function solution(n, edge) {
	// 그래프 초기화
    const graph = Array.from(Array(n+1), () => []);
    // 노드1로부터 각 노드당 거리 0으로 초기화 한 배열
    const distance = Array(n+1).fill(0);
    // 노드1은 이미 방문했으니 1로 초기화
    distance[1] = 1;
    
    // 각 간선들 그래프에 그려주기
    for(const [src, dest] of edge) {
        graph[src].push(dest);
        graph[dest].push(src);
    }
    
    // BFS
    const queue = new Queue();
    // 노드1 부터 시작이므로 queue에 1 삽입
    queue.enqueue(1);
    
    while(!queue.isEmpty()) {
    	// dequeue한 노드가 현재 노드
        const src = queue.dequeue();
        // 그래프에서 현재 노드의 목적지들 순회
        for(const dest of graph[src]) {
        	// 현재 노드로부터 목적지의 거리가 0이라면 즉, 아직 방문을 안했다면
            if(distance[dest] === 0) {
            	// queue에 목적지 노드 삽입
                queue.enqueue(dest);
                // 목적지까지의 거리를 노드1부터 현재노드까지의 거리 + 1로 갱신
                distance[dest] = distance[src] + 1;
            }
        }
    }
    
    // 각 노드까지의 거리의 최댓값을 구한 후
    const maxDistance = Math.max(...distance);
    // 거리 배열에서 최댓값과 같은 요소들의 개수를 리턴
    return distance.filter(item => item === maxDistance).length
}

 

후기

일전에 queue를 이용해야 하는 문제에서 queue를 빈배열로 두고 push와 shift를 통해 임의적으로 queue를 구현하여 문제를 푼 경험이 있는데, 이는 말 그대로 임의로 구현한 queue이기 때문에 enqueue동작은 O(1)의 시간이 걸리지만 dequeue동작에는 O(n)의 시간이 걸리므로 효율적이지 못하다는 피드백을 들었다. 앞으로는 queue를 사용해야 하는 상황에 queue를 구현하는 습관을 가져야겠다고 생각하게 된 문제였다.