https://school.programmers.co.kr/learn/courses/30/lessons/118669
XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.
등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.
당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.
다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.
- 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.
위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다. 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.
등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.
등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.
이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.
XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.
제한사항
- 2 ≤ n ≤ 50,000
- n - 1 ≤ paths의 길이 ≤ 200,000
- paths의 원소는 [i, j, w] 형태입니다.
- i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
- w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
- 1 ≤ i < j ≤ n
- 1 ≤ w ≤ 10,000,000
- 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
- 1 ≤ gates의 길이 ≤ n
- 1 ≤ gates의 원소 ≤ n
- gates의 원소는 해당 지점이 출입구임을 나타냅니다.
- 1 ≤ summits의 길이 ≤ n
- 1 ≤ summits의 원소 ≤ n
- summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
- 출입구이면서 동시에 산봉우리인 지점은 없습니다.
- gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
- 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
- return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.
첫번째 풀이 (실패)
출입구에서 산봉우리까지 최소 intensity를 찾으면 동일한 경로대로 산봉우리에서 출입구까지 이동하면 되므로
출입구-산봉우리-출입구 경로의 최소 intensity를 찾는 대신, 출입구-산봉우리 경로의 최소 intensity만 찾아도 문제를 해결할 수 있다.
각 출입구마다 bfs로 순회를 돌며 intensity를 정리했다.
intensity[ i ] = 출입구A에서 i 지점까지 오는데 최댓값
function solution(n, paths, gates, summits) {
var answer = {
summit: Infinity,
intense: Infinity,
};
const summitSet = new Set(summits);
const graph = Array.from({ length: n + 1 }, () => []); // [[], [{to: 2, d: 3}], [{to:}]]
// 그래프정리
for (const [from, to, d] of paths) {
graph[from].push({ to, d });
graph[to].push({
to: from,
d,
});
}
for (const gate of gates) {
const intensity = Array.from({ length: n + 1 }, () => Infinity);
intensity[gate] = 0;
const queue = [{ to: gate, d: 0, isReached: false }];
while (queue.length) {
const currNode = queue.shift();
for (const nextNode of graph[currNode.to]) {
// 이미 정상을 방문했는데 정상을 재방문할 수 없다.
if (currNode.isReached && summitSet.has(nextNode.to)) {
continue;
}
const newDistance = Math.max(intensity[currNode.to], nextNode.d); // 돌아오는 길에 정상에서 다른 지역으로 이동거리도 고려
if (intensity[nextNode.to] > newDistance) {
intensity[nextNode.to] = newDistance;
queue.push({
...nextNode,
isReached: currNode.isReached || summitSet.has(nextNode.to),
});
}
}
}
summits.forEach((summit) => {
const currMaxIntensity = intensity[summit];
if (answer.intense > currMaxIntensity) {
answer = {
summit,
intense: currMaxIntensity,
};
} else if (
answer.intense === currMaxIntensity &&
answer.summit > summit
) {
answer = {
summit,
intense: currMaxIntensity,
};
}
});
}
return [answer.summit, answer.intense];
}
아무리 생각해도 더이상 방법이 생각나지 않아 해설을 보며 다익스트라 우선순위 큐에 대해 공부했다.
두번째 풀이 (성공)
https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/
주요 포인트
- 출입구-산봉우리 경로의 최소경로 값만 구하면 된다. (하산할때 올라갔던 길 그대로 내려오면 되기 때문이다.)
- 특정 노드에서 특정 노드까지의 최소 경로값을 구한다 => 다익스트라
- 다익스트라를 구현하기 위해
- 빠르게 주변노드를 찾기위해 객체로 인접리스트 그래프를 구현한다. ( 출발점 : [{nextNode, nextIntensity}] 형태로 가중치까지 넣어야 후에 가중치를 비교할 수 있다. )
- 각 노드마다 최소 경로값을 저장하는 IntensityArr를 만들고 Infinity (10000001)로 초기화한다.
- 최소 경로를 우선적으로 찾기위해 MinHeap 클래스를 구현한다 (push, pop)
- 우선순위 큐 클래스를 구현했으면 우선순위 큐에 gates출입구를 먼저 순회하며 {노드 값: gate, 가중치: 0} 형태로 push한다. 이때 gate 스스로의 가중치는 0이다
- 이제 큐에서 pop한 노드들을 방문하며 이웃 노드 중 가중치를 갱신해야하는 노드들을 큐에 push하고 가중치를 갱신한다. (이 과정은 아래에 더 자세하게 정리했다)
- 더 이상 방문할 노드가 없을 때 (큐에 노드가 없을때)까지 위의 과정을 실행하고 나면 IntensityArr에 각 노드까지 최소경로값이 저장된다
- gates를 순회하며 최소intensity와 최소 정상을 찾아내어 반환한다.
위의 과정 중 우선순위큐에 노드를 push, pop하며 가중치를 갱신하는 과정을 더 자세하게 살펴보자
- gate 시작 노드를 {가중치, 노드 값} 형태로 큐에 넣는다.
- 큐에서 curr노드를 pop한다.
- curr의 이웃인 around마다 (curr의 가중치와 around까지의 가중치)를 비교하여 최대값을 around의 새로운 가중치로 구한다. Max( curr 가중치, around 가중치 )
- 3에서구한 around의 새로운 가중치가 이전 가중치인 IntensityArr[around]보다 작으면 Min heap에 push하고 가중치를 갱신한다.
- 이때 MinHeap에 넣으면 자동으로 가중치가 작은 순으로 정렬된다.
- 단 이미 방문한 곳은 큐에 넣지 않는다 (우선순위 덕분에 이미 방문한 곳의 가중치는 현재 가중치보다 작거나 같으므로)
위 그림에서 현재노드curr, 주변노드around이고, curr까지 가중치는 5, curr에서 around까지의 가중치는 6일때,
curr까지의 가중치5와 curr에서 around까지의 가중치6 중 최대값인 6은 around까지 가중치의 새로운 값이다.
이것을 이전의 around까지 가중치인 Infinity 와 비교하면 6이 최소값이고 이는 around까지의 최소경로값이다.
새로운 최소경로값을 구했으니 InfinityArr를 갱신하고 우선순위 큐에 push하여 계속 최소경로를 구한다.
전체코드
// 1~n, 출입구, 쉼터, 산봉우리, 양방향
// intensity: 휴식없이 이동하는 최장시간
// 출입구중 한 곳에서 출발, 산봉우리 한곳만 방문 후 다시 원래 출입구로 돌아옴
// intensity가 최소가 되는 [산봉우리번호, intensity 최소값] 리턴, intensity최소가 여러개이면 낮은 산봉우리
// 올라갔던 길을 다시 그대로 내려오면 된다
// => 한 출입구에서 한 산봉우리까지 intensity 정리
// 최소 intensity 찾기
function solution(n, paths, gates, summits) {
const summitSet = new Set(summits); // 산봉우리인지 확인 O(1)
// 양방향 그래프 정리
const graph = {}; // {'1': [ { nextNode: 2, nextIntensity: 3 } ]}
paths.forEach(([fromNode, toNode, intensity]) => {
// 새로운 노드면 초기화
if (!(fromNode in graph)) graph[fromNode] = [];
if (!(toNode in graph)) graph[toNode] = [];
// 노드와 연결된 path
graph[fromNode].push({ nextNode: toNode, nextIntensity: intensity });
graph[toNode].push({ nextNode: fromNode, nextIntensity: intensity });
});
// 가중치 작은 순서대로 큐에 넣고 빼기 위해 최소힙을 사용한다.
const minQueue = new MinHeap();
// memo[i] = i번 노드까지 가는데 필요한 최대 가중치
const memo = Array.from({ length: n + 1 }, () => Infinity); // 10000001
// 먼저 출입구부터 큐에 넣는다
gates.forEach((gate) => {
minQueue.push({ intensity: 0, node: gate });
memo[gate] = 0; // 출입구의 가중치는 0
});
while (minQueue.heap.length > 1) {
// 현재노드, 현재노드 까지 필요한 최대가중치
const { intensity: currIntensity, node } = minQueue.pop();
// 현재노드가 정상이거나 현재 가중치가 이미 기존가중치보다 크면 현재노드에서 탐색을 멈춘다 (이미 최소가중치를 넘었기때문에 더이상 탐색할 필요없다)
if (summitSet.has(node) || currIntensity > memo[node]) {
continue;
}
// // 그래프에 없는 노드일때
// if (!(node in graph)) {
// continue;
// }
// 현재노드와 연결된 다음 노드들을 순회한다
graph[node].forEach(({ nextIntensity, nextNode }) => {
// 새로운 가중치 = 현재까지 최대가중치와 현재노드에서 다음노드로 가는 가중치 중 큰 값
const newIntensity = Math.max(currIntensity, nextIntensity);
// 새로운 가중치가 기존가중치보다 작으면
if (newIntensity < memo[nextNode]) {
memo[nextNode] = newIntensity; // 기존가중치를 새로운 가중치로 갱신하고
minQueue.push({ node: nextNode, intensity: newIntensity }); // 큐에 추가하여 다음으로 연결된 노드들의 가중치를 갱신한다.
}
});
}
summits.sort((a, b) => a - b); // 작은 정상 우선
// 정상
const answer = [0, Infinity];
summits.forEach((summit) => {
if (memo[summit] < answer[1]) {
answer[0] = summit;
answer[1] = memo[summit];
}
});
return answer;
}
// intensity 최소우선순위큐
class MinHeap {
constructor() {
this.heap = [null];
}
push(data) {
const { intensity, node } = data;
let currIndex = this.heap.length;
// 부모노드가 존재할때 현재노드의 제 위치를 찾는다
while (currIndex > 1) {
const parentIndex = Math.floor(currIndex / 2);
// 부모 > 현재이면 swap
if (this.heap[parentIndex].intensity > intensity) {
[this.heap[currIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[currIndex],
];
currIndex = parentIndex;
} else {
break;
}
}
this.heap[currIndex] = { intensity, node };
}
pop() {
const min = this.heap[1];
// 자식노드가 있을떄
if (this.heap.length > 2) {
// 마지막 노드를 최상위 노드로 올려준다
this.heap[1] = this.heap.pop();
let currIndex = 1;
let leftChildIndex = currIndex * 2;
let rightChildIndex = currIndex * 2 + 1;
// 자식이 있을 때
while (this.heap[leftChildIndex]) {
// 두 자식중 intensity최소자식 구하기
let smallerChildIndex = leftChildIndex;
if (
this.heap[rightChildIndex] &&
this.heap[leftChildIndex].intensity >
this.heap[rightChildIndex].intensity
) {
smallerChildIndex = rightChildIndex;
}
// 부모 > 최소자식이면 둘을 swap
if (
this.heap[currIndex].intensity >
this.heap[smallerChildIndex].intensity
) {
[this.heap[currIndex], this.heap[smallerChildIndex]] = [
this.heap[smallerChildIndex],
this.heap[currIndex],
];
currIndex = smallerChildIndex;
} else {
break;
}
leftChildIndex = currIndex * 2;
rightChildIndex = currIndex * 2 + 1;
}
return min;
} else if (this.heap.length === 2) {
this.heap.pop();
} else {
return null;
}
return min;
}
}
'알고리즘' 카테고리의 다른 글
| [프로그래머스] 코딩테스트 공부 (0) | 2023.11.25 |
|---|---|
| 우선순위 큐, 힙 (0) | 2023.11.22 |
| [레벨2] n^2 배열 자르기 (0) | 2023.11.03 |
| [프로그래머스 LV2] 연속 부분 수열 합의 개수 JS (0) | 2023.11.03 |
| [다익스트라 레벨3] 부대복귀 (0) | 2023.11.03 |
