부대복귀
문제 설명
강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.
강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.
문제 요약
n개의 노드가 있다.roads에 연결관계가 있다.sources에서destination까지 가는 최단 거리를 구해라- 도착이 불가능 하면 -1
입출력 예
| n | roads | sources | destination | result |
|---|---|---|---|---|
| 3 | [[1, 2], [2, 3]] | [2, 3] | 1 | [1, 2] |
| 5 | [[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]] | [1, 3, 5] | 5 | [2, -1, 0] |
풀이 과정
위의 문제는 가중치를 포함한 최소 거리를 구하는 문제이다.
이런 문제의 경우 가중치가 모두 양수라면 다익스트라(Dijkstra) 알고리즘일 가능성이 크다.
따라서 다익스트라(Dijkstra)를 이용해서 풀 예정이고 풀이를 보기 전에
다익스트라(Dijkstra) 알고리즘은 기본적으로 BFS(너비 우선 탐색)를 기반으로 구현을 한다.
여기서 구현 방식에 따라서 2가지 방식으로 나뉘는데 그것은 아래에서 자세히 설명하겠다.
다익스트라(Dijkstra) 알고리즘 구현
다익스트라(Dijkstra) 구현 방식은
- 순차 탐색을 이용하여 거리 테이블을 매번 확인하는 방식
- 우선순위 큐 (Priority Queue)를 이용하여 최단거리를 우선 탐색하는 방식
두가지 방식이 있다.
우선 순차 탐색을 이용하여 거리 테이블을 매번 확인 하는 방식인데 우리가 필요한게 2가지 있다.
-
우선 특정 지점부터 해당 노드까지 가는 거리를 담는 배열
ex)[Infinity, 0(시작 노드), 2번 노드까지의 거리, ....] -
연결 관계가 나와 있는 인접 리스트
인접 리스트, 거리 배열 생성
// n+1을 하는 이유는 노드 번호로 배열을 사용하기 위해
const trees = new Array(n + 1).fill().map(_ => []);
for (let i = 0; i < roads.length; i++) {
trees[roads[i][0]].push(roads[i][1]);
trees[roads[i][1]].push(roads[i][0]);
}
// 거리배열은 거리가 최대 값이 되도록 초기화
// 거리에 최대 값이 있으면 굳이 Infinity로 설정 안해도됨
let visited = new Array(n + 1).fill(Infinity);
앞서 말했듯 다익스트라(Dijkstra) 알고리즘은 BFS를 기반으로 구현하기 때문에
우리가 알고 있는 익숙한 BFS느낌의 함수가 있다.
BFS의 로직은 다음과 같은 순서로 진행이 된다.
- 시작 지점을 매개변수로 받아서
shortest배열에 시작 지점을 0으로 변경 - 시작부분부터 시작하여
trees배열에 있는 연결 되어있는 노드를 검사- 만약 해당 지점의
shortest값이 현재 지점의shortest값 +1 보다 크면 값 변경 - 그 후 큐에 다음 위치 삽입
- 만약 해당 지점의
BFS문
const BFS = (goal) => {
shortest[goal] = 0;
let queue = [goal];
while (queue.length) {
let now = queue.shift();
for (let i = 0; i < trees[now].length; i++) {
// now 노드와 연결된 다음 노드의 visited 배열 값 비교
if (shortest[now] + 1 < shortest[trees[now][i]]) {
shortest[trees[now][i]] = shortest[now] + 1;
queue.push(trees[now][i]);
}
}
}
};위의 과정을 거치면 거리 배열에 시작 지점은 0으로, 다른 지점의 값은 최소값 혹은 가는것이 불가능하면 Infinity 값이 들어가 있다.
문제 요구 사항에서 불가능할 경우 -1을 리턴해주라고 했기 때문에 해당 과정을 추가하면 된다.
전체 코드
function solution(n, roads, sources, destination) {
const trees = new Array(n + 1).fill().map(_ => []);
let answer = [];
for (let i = 0; i < roads.length; i++) {
trees[roads[i][0]].push(roads[i][1]);
trees[roads[i][1]].push(roads[i][0]);
}
let shortest = new Array(n + 1).fill(Infinity);
const BFS = (goal) => {
shortest[goal] = 0;
let queue = [goal];
while (queue.length) {
let now = queue.shift();
for (let i = 0; i < trees[now].length; i++) {
if (shortest[now] + 1 < shortest[trees[now][i]]) {
shortest[trees[now][i]] = shortest[now] + 1;
queue.push(trees[now][i]);
}
}
}
};
BFS(destination);
for (const army of sources) {
if (shortest[army] === Infinity) {
answer.push(-1);
}else{
answer.push(shortest[army]);
}
}
return answer;
}그럼 이제 우선 순위 큐(Priority Queue)를 이용하여 풀어보자.
전에 있었던 백준 문제 에서도 말했지만
JavaScript에서는 우선순위 큐를 라이브러리로 제공하지 않아서 우리가 직접 구현을 해야한다.
따라서 전에 만들었던 우선순위 큐 구현 코드를 조금 수정하여 사용할 예정이다.
그런데 그 전에 우리는 우선 순위 큐에 {node: ?, cost: ?} 형태로 넣어줄 예정이고 cost를 기준으로 MinHeap을 만들 것이다.
그리고 만약 cost가 같을 경우 node가 더 작은 값을 우선으로 배치할 예정이다.
수정한 MinHeap을 이용한 우선순위 큐 구현 코드
class MinHeap {
constructor() {
this.heap = [null];
}
insert(item) {
// 트리의 마지막 위치부터 순서대로 계산
let current = this.heap.length;
while (current > 1) {
const parent = Math.floor(current / 2);
// cost 비교 후 위치 변경
if (this.heap[parent].cost > item.cost) {
this.heap[current] = this.heap[parent];
current = parent;
// 만약 cost 가 같을 경우 node를 기준으로 위치 변경
} else if (this.heap[parent].cost === item.cost) {
if (this.heap[parent].node > item.node) {
this.heap[current] = this.heap[parent];
current = parent;
} else break;
} else break;
}
//current 값이 위의 반복문을 통해 알맞은 위치로 왔다. 따라서 핻당 위치에 값 배치
this.heap[current] = item;
}
remove() {
let min = this.heap[1];
if (this.heap.length > 2) {
// 우선순위 큐에서 최상단을 제거하기 때문에 최상단 제거
// 마지막 위치의 노드에 있는 값을 최상단으로 옮김
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.splice(this.heap.length - 1);
// 최상단부터 아래로 내려가며 비교
let current = 1;
let leftChild = current * 2;
let rightChild = current * 2 + 1;
// 이진 트리이기 때문에 왼쪽 자식이 있는 것으로 자식 노드가 있는지 판단
while (this.heap[leftChild]) {
let compareItem = leftChild;
// 오른쪽 자식이 있을 경우, 왼쪽 자식과 오른쪽 자식 노드 비교
// 비교 후 compareItem에 내가 비교할 노드 저장
if (this.heap[rightChild] && this.heap[compareItem].cost > this.heap[rightChild].cost) {
compareItem = rightChild;
} else if (this.heap[rightChild] && this.heap[compareItem].cost === this.heap[rightChild].cost) {
if (this.heap[compareItem].node > this.heap[rightChild].node) {
compareItem = rightChild;
}
}
// 위의 과정으로 더 작은 자식 노드가 compareItem에 들어간다.
// 따라서 compareItem과 부모 노드를 비교
// 만약 자식 노드가 더 클 경우 위치 변경
if (this.heap[current].cost > this.heap[compareItem].cost) {
[this.heap[current], this.heap[compareItem]] = [this.heap[compareItem], this.heap[current]];
current = compareItem;
} else if (this.heap[current].cost === this.heap[compareItem].cost) {
if (this.heap[current].node > this.heap[compareItem].node) {
[this.heap[current], this.heap[compareItem]] = [this.heap[compareItem], this.heap[current]];
// 위치 변경후 해당 위치에서 다시 반복문 진행
current = compareItem;
} else break;
} else break;
// current 값이 바뀌었기 때문에 자식 노드도 바꿔줌
leftChild = current * 2;
rightChild = current * 2 + 1;
}
} else if (this.heap.length === 2) {
this.heap.splice(1, 1);
} else {
return null;
}
return min;
}
getMin() {
return this.heap[1];
}
getSize() {
return this.heap.length - 1;
}
getHeap() {
return this.heap;
}
}
이제 우선순위 큐가 구현이 되었으니 로직을 순서대로 생각해보자.
우리는 우선순위 큐에 cost가 작은 값들이 들어올 예정이다.
여기서 cost는 해당 node까지 가는 거리를 나타내는 것
그럼 table에 거리를 기록한 shortest 배열이 필요하고, 해당 노드를 이미 거쳤는지 확인할 visited 배열도 필요하다.
그리고 트리의 연결 관계를 저장했던 trees 변수에도 heap의 구조에 맞게 {node: ? , cost: ?} 형태로 저장을 해야한다.
변수 생성 코드
let answer = [];
let list = Array.from({length: n + 1}, () => []);
for (let i = 0; i < roads.length; i++) {
const [start, end] = roads[i];
list[start].push({node: end, cost: 1});
list[end].push({node: start, cost: 1});
}
let shortest = Array.from({length: n + 1}, () => Infinity);
const visited = new Array(n + 1).fill(false);
const priorityQueue = new MinHeap();
그 외의 코드는 BFS와 똑같지만, BFS에서 반복문을 돌 때 사용하는 Queue 대신 우선순위 큐 (Priority Queue)를 사용한다고 생각하면 된다.
BFS 기반의 로직 코드
// 시작 지점 값 초기화
priorityQueue.insert({node: destination, cost: 0});
shortest[destination] = 0;
// 우선순위 큐를 이용한 BFS기반의 코드
while (priorityQueue.getSize()) {
const TopOfPrioriyQueue = priorityQueue.remove();
const now = TopOfPrioriyQueue.node;
// 현 위치 값의 visited를 체크
if (!visited[now]) {
visited[now] = true;
// 반복문으로 연결되어 있는 노드를 돌며 최단거리 갱신
// 최단 거리 갱신 후 다음 노드와 cost를 증가 시켜주고 우선 순위큐에 삽입
for (const node of list[now]) {
const pathNodeCost = node.cost;
const fullCost = TopOfPrioriyQueue.cost + pathNodeCost;
shortest[node.node] = Math.min(shortest[node.node], fullCost);
priorityQueue.insert({node: node.node, cost: fullCost});
}
}
}
전체 코드
class MinHeap {
constructor() {
this.heap = [null];
}
insert(item) {
// 트리의 마지막 위치부터 순서대로 계산
let current = this.heap.length;
while (current > 1) {
const parent = Math.floor(current / 2);
// cost 비교 후 위치 변경
if (this.heap[parent].cost > item.cost) {
this.heap[current] = this.heap[parent];
current = parent;
// 만약 cost 가 같을 경우 node를 기준으로 위치 변경
} else if (this.heap[parent].cost === item.cost) {
if (this.heap[parent].node > item.node) {
this.heap[current] = this.heap[parent];
current = parent;
} else break;
} else break;
}
//current 값이 위의 반복문을 통해 알맞은 위치로 왔다. 따라서 핻당 위치에 값 배치
this.heap[current] = item;
}
remove() {
let min = this.heap[1];
if (this.heap.length > 2) {
// 우선순위 큐에서 최상단을 제거하기 때문에 최상단 제거
// 마지막 위치의 노드에 있는 값을 최상단으로 옮김
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.splice(this.heap.length - 1);
// 최상단부터 아래로 내려가며 비교
let current = 1;
let leftChild = current * 2;
let rightChild = current * 2 + 1;
// 이진 트리이기 때문에 왼쪽 자식이 있는 것으로 자식 노드가 있는지 판단
while (this.heap[leftChild]) {
let compareItem = leftChild;
// 오른쪽 자식이 있을 경우, 왼쪽 자식과 오른쪽 자식 노드 비교
// 비교 후 compareItem에 내가 비교할 노드 저장
if (this.heap[rightChild] && this.heap[compareItem].cost > this.heap[rightChild].cost) {
compareItem = rightChild;
} else if (this.heap[rightChild] && this.heap[compareItem].cost === this.heap[rightChild].cost) {
if (this.heap[compareItem].node > this.heap[rightChild].node) {
compareItem = rightChild;
}
}
// 위의 과정으로 더 작은 자식 노드가 compareItem에 들어간다.
// 따라서 compareItem과 부모 노드를 비교
// 만약 자식 노드가 더 클 경우 위치 변경
if (this.heap[current].cost > this.heap[compareItem].cost) {
[this.heap[current], this.heap[compareItem]] = [this.heap[compareItem], this.heap[current]];
current = compareItem;
} else if (this.heap[current].cost === this.heap[compareItem].cost) {
if (this.heap[current].node > this.heap[compareItem].node) {
[this.heap[current], this.heap[compareItem]] = [this.heap[compareItem], this.heap[current]];
// 위치 변경후 해당 위치에서 다시 반복문 진행
current = compareItem;
} else break;
} else break;
// current 값이 바뀌었기 때문에 자식 노드도 바꿔줌
leftChild = current * 2;
rightChild = current * 2 + 1;
}
} else if (this.heap.length === 2) {
this.heap.splice(1, 1);
} else {
return null;
}
return min;
}
getMin() {
return this.heap[1];
}
getSize() {
return this.heap.length - 1;
}
getHeap() {
return this.heap;
}
}
function solution(n, roads, sources, destination) {
let answer = [];
let list = Array.from({length: n + 1}, () => []);
for (let i = 0; i < roads.length; i++) {
const [start, end] = roads[i];
list[start].push({node: end, cost: 1});
list[end].push({node: start, cost: 1});
}
let shortest = Array.from({length: n + 1}, () => Infinity);
console.log(list);
const priorityQueue = new MinHeap();
const visited = new Array(n + 1).fill(false);
// 시작 지점 값 초기화
priorityQueue.insert({node: destination, cost: 0});
shortest[destination] = 0;
// 우선순위 큐를 이용한 BFS기반의 코드
while (priorityQueue.getSize()) {
const TopOfPrioriyQueue = priorityQueue.remove();
const now = TopOfPrioriyQueue.node;
// 현 위치 값의 visited를 체크
if (!visited[now]) {
visited[now] = true;
// 반복문으로 연결되어 있는 노드를 돌며 최단거리 갱신
// 최단 거리 갱신 후 다음 노드와 cost를 증가 시켜주고 우선 순위큐에 삽입
for (const node of list[now]) {
const pathNodeCost = node.cost;
const fullCost = TopOfPrioriyQueue.cost + pathNodeCost;
shortest[node.node] = Math.min(shortest[node.node], fullCost);
priorityQueue.insert({node: node.node, cost: fullCost});
}
}
}
// 출력을 위해 answer 배열에 삽입
for (let i = 0; i < sources.length; i++) {
if (shortest[sources[i]] === Infinity) {
answer.push(-1);
} else {
answer.push(shortest[sources[i]]);
}
}
return answer;
}
JavaScript를 사용하는 모두를 위해...