[LeetCode] 882. Reachable Nodes In Subdivided Graph

문제 출처: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/

Reachable Nodes In Subdivided Graph - LeetCode

---

문제

0 ~ n-1로 이름 붙여진 n개의 노드로 구성된 무방향 그래프("오리지널 그래프")가 주어진다. 당신은 그래프의 간선을 세세하기 나누고 새로운 노드를 만들어 넣기로 하였다.

 

그래프는 2차원 배열 edges로 주어지지고, $edges[i] = [u_i, v_i, cnt_i]$는 오리지널 그래프에서 $u_i$ 노드와 $v_i$ 노드가 연결되어 있으며, 해당 간선에 $cnt_i$개의 새로운 노드를 만들겠다는 것이다. $cnt_i == 0$ 은 간선을 나누지 않겠다는 의미이다.

 

간선 $[u_i, v_i]$를 나누기 위해서, ($cnt_i$)개의 새로운 간선과 $cnt_i$개의 새 노드를 만들어 넣는다. 새 노드는 $x_1, x_2, ..., x_{cnt i}$ 이고 새로운 간선은 $[u_i, x_1], [x_1, x_2], [x_2, x_3], ... [x_{cnt j}, v_i]$ 이다.

 

이 새로운 그래프에서, 0에서 부터 얼마나 많은 노드들이 닿을 수 있는지 알고 싶다. 한 노드가 0에서 maxMoves 이내에 도착 가능한 거리라면, 닿을 수 있다고 말한다.

 

오리지널 그래프와 maxMoves가 주어지면, 새로운 그래프에서 0 노드에서 시작하여 닿을 수 있는 노드의 개수를 반환하라.

예제

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13

Explanation: The edge subdivisions are shown in the image above.
The nodes that are reachable are highlighted in yellow.

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23

Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
Output: 1

Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.

---

풀이

이 문제의 핵심은 "다익스트라 알고리즘을 떠올릴 수 있는가" 라고 생각합니다.

 

다익스트라 알고리즘은 그래프에서 시작점이 주어질 때, 시작점으로부터 간선을 타고 이동할 수 있는 모든 노드에 대한 최단 거리를 구하는 알고리즘입니다.

 

다익스트라 코드를 작성하기 전에, 한 가지 사항을 생각해보아야 합니다.  "세분화된(subdivied) 간선 노드를 어떻게 취급할 것인가?" 문제에서 새로운 노드라고 말하고 있으니, 문자 그대로 노드로 생각해야 하나? 이 질문에 대한 답은 "간선의 가중치(weight)"로 생각하는 것입니다.

 

※ 만약, 세분화된 간선 노드를 실제 노드로 생각하고 문제를 바라본다면?

• 굳이 다익스트라 알고리즘을 적용할 필요 없이 기본적인 그래프 탐색 알고리즘(DFS 또는 BFS)을 이용하여 문제를 풀 수 있습니다.
• 하지만, 최악의 경우 3,000개의 노드가 서로 연결되어 있는 그래프의 각 간선에 10^4개의 새로운 노드가 추가되는 케이스를 생각해 볼 수 있습니다. 이 경우, 단순 노드의 개수만 생각해도 메모리가 버틸 수 있을까요?

 

이제 문제의 입력을 기반으로 하여 기본적인 다익스트라 알고리즘을 적용하면 다음과 같은 코드가 됩니다.

var reachableNodes = function(edges, maxMoves, n) {
    let answer = 0;
    
    // 입력 edges를 기반으로, 입접리스트를 만들기
    const adj = Array(n).fill(0).map(val => []);
    for (let [u, v, w] of edges) {
    	adj[u].append([v, w]);
        adj[v].append([u, w]);
    }
    
    // dist = 0번째 노드에서부터 각 노드까지의 거리를 저장할 배열
    const dist = Array(n).fill(maxMoves + 1);
    dist[0] = 0;
    
    const queue = [[0, 0]]; // 우선순위 큐 처럼 이용한 배열, item = [dist, node]
    while (queue.length) {
    	const [d, node] = queue.shift();
        
        // 최단 거리 여부 체크
        if (d > dist[n]) { continue; }
        answer += 1;
        
        // 현재 노드에서 이동 가능한 다른 노드 찾기
        for (let [dn, neighbor] of adj[node]) {
            // 현재 노드를 거쳐 neighbor로 갈 경우의 거리 계산
            const totalDist = d + dn + 1;
            
            // 현재 노드를 거쳐 neighbor로 가는게 기존 알고 있는 것보다
            // 더 짧다면(빠르다면) 교체
            if (totalDist < dist[neighbor]) {
            	dist[neighbor] = totalDist;
                queue.push([totalDist, neighbor]);
            }
        }
        
        // 배열을 우선순위 큐 처럼 사용하기 위해, 정렬
        queue.sort((a, b) => a[0] - b[0]);
    }
    
    return answer;
}

이 기본적인 다익스트라 알고리즘 만으로 체크되는 노드를 그림으로 그려보자. 예를 들어, edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3 일 때, answer 변수를 증가시키는 노드는 아래 노란색으로 표시한 노드입니다.

당연하게도 간선에 만들어지는 노드를 가중치화한 상태로 다익스트라 알고리즘을 돌렸기 때문입니다.

 

이제 간선에 새로 생기는 노드를 취급하기 위해 기본 다익스트라 알고리즘에 몇 가지 코드를 추가할 텐데, 코드는 다음과 같습니다. 

var reachableNodes = function(edges, maxMoves, n) {
    let answer = 0;
    
    const adj = Array(n).fill(0).map(val => []);
    for (let [u, v, w] of edges) {
    	adj[u].append([v, w]);
        adj[v].append([u, w]);
    }
        
    const dist = Array(n).fill(maxMoves + 1);
    dist[0] = 0;
    
    // 방문할 수 있는 간선 노드를 체크하기 위한 공간
    const used = new Map();
    
    const queue = [[0, 0]];
    while (queue.length) {
    	const [d, node] = queue.shift();
        
        if (d > dist[n]) { continue; }
        answer += 1;
        
        for (let [dn, neighbor] of adj[node]) {
            // node => neighbor로 갈 때, 몇 개의 간선 노드를 방문가능 한지 계산
            used.set(`${node}to${neighbor}`, Math.min(dn, maxMoves - d))
        
            const totalDist = d + dn + 1;
            
            if (totalDist < dist[neighbor]) {
            	dist[neighbor] = totalDist;
                queue.push([totalDist, neighbor]);
            }
        }
        
        queue.sort((a, b) => a[0] - b[0]);
    }
    
    return answer;
}

기존의 코드에 used라는 이름의 맵 자료구조를 취급하는 변수를 선언 및 인접한 노드를 순회하면서 큐를 갱신하는 반복문에서 used에 값을 업데이트하는 코드가 추가되었습니다.

 

used는 키는 간선이 어떤 노드들을 연결하는 간선인지, 어느 방향인지를 포함할 수 있도록 "{from_node}to{to_node}"의 형식으로 저장하며, 값은 min(간선의 가중치, 남아있는 움직임 수)가 된다.

 

무방향 그래프임에도 방향을 신경 쓰는 이유는 아래 그림과 같이 0에서 1로 도달이 불가능하고, 1에서도 0으로 도달이 불가능할 때, 각각 몇 개의 간선 노드를 사용할 수 있는지 체크하기 위함입니다.

이제 answer를 업데이트시켜보면 다음과 같습니다.

var reachableNodes = function(edges, maxMoves, n) {
    let answer = 0;
    
    const adj = Array(n).fill(0).map(val => []);
    for (let [u, v, w] of edges) {
    	adj[u].append([v, w]);
        adj[v].append([u, w]);
    }
        
    const dist = Array(n).fill(maxMoves + 1);
    dist[0] = 0;
    
    const used = new Map();
    
    const queue = [[0, 0]];
    while (queue.length) {
    	const [d, node] = queue.shift();
        
        if (d > dist[n]) { continue; }
        answer += 1;
        
        for (let [dn, neighbor] of adj[node]) {
            used.set(`${node}to${neighbor}`, Math.min(dn, maxMoves - d))
        
            const totalDist = d + dn + 1;
            
            if (totalDist < dist[neighbor]) {
            	dist[neighbor] = totalDist;
                queue.push([totalDist, neighbor]);
            }
        }
        
        queue.sort((a, b) => a[0] - b[0]);
    }
    
    // 모든 edge의 used를 확인하면서 접근 가능한 간선 노드 개수 카운트
    for (let [u, v, w] of edges) {
    	used1 = used.get(`${u}to${v}`)
        used2 = used.get(`${v}to${u}`)
        answer += Math.min(w, used1 + used2)
    }
    
    return answer;
}

 

Github: 882.js

GitHub - opwe37/Algorithm-Study