[JS|정렬] 프로그래머스 62050번. 지형이동 (프림 알고리즘, 크루스칼 알고리즘)

 

 

문제 보러 가기 ⬆︎

 

---

1. 입력과 출력

• 입력
  • N x N 크기의 2차원 배열 land ( 4 ≤ N ≤ 300 ) : 원소는 각 칸의 높이를 나타냄
  • 칸끼리 이동 가능한 최대 높이 차 height ( 1 ≤ height ≤ 10,000 )

• 출력
  • 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값 return : answer

 

2. 문제 풀이 로직

문제를 읽고 어떻게 풀까.. 고민하다가 이동 가능한 그룹이 나뉘어져 있고, 사다리를 놓아서 최소 비용으로 모든 칸을 돌 수 있어야하기 때문에 가장 중요한 것은 '어떻게 이동 가능한 그룹을 나눌것인가'와 '어떻게 최소 비용으로 사다리를 놓을 수 있을까?'였다.

먼저 이동 가능한 그룹을 나누기 위해서는 BFS로 인접한 상하좌우로 살펴보며 움직일 수 있는 칸인지 확인하는 과정을 거치며 사다리 없이도 움직일 수 있는 그룹을 만드는 것이 중요하였다. 어? 이것은 최소 신장 트리를 사용하는 문제라고 생각하였다. 최소 신장 트리(Minimum Spanning Tree, MST)가 무엇이냐면... 다음과 같은 트리가 있을 경우 모든 노드를 탐색하는데 최소 경로로만 이뤄진 비순환 트리를 뜻한다.

최소 신장 트리

 

그렇다면 생각나는 알고리즘이 두 개 있다. 바로 프림 알고리즘과 크루스칼 알고리즘이다. 둘 다 최소 신장 트리를 구하거나 사용하는 알고리즘이며, 지형 이동 문제에 어울리는 알고리즘을 선택하기 위해서는 당연하게도 알고리즘에 대해 제대로 알고 가야 하기에 두 알고리즘 각각의 특징을 알아보고 비교를 해보려고 한다.

 

최소 신장 트리를 사용하는 알고리즘

1. 프림 알고리즘

- 정점 중심의 알고리즘

- 우선순위 큐(Priotity Queue) 사용 : 최소 비용 간선 탐색용

 

알고리즘 과정 그림으로 살펴보기

① 임의의 노드 하나를 선택하여 시작 지점으로 정하기

② 방문하지 않은 노드 중 방문 가능한 가장 가까운 노드를 선택하기 (-> 우선순위 큐 사용)

 

 

③ 모든 노드를 탐색하여 선택된 간선의 개수가 노드-1개라면 탐색 종료

 

---

2. 크루스칼 알고리즘

- 간선 중심의 알고리즘

- 유니온-파인드(Unio-Find) 사용 : 그래프 순환 여부 확인용

 

알고리즘 과정 그림으로 살펴보기

① 간선들을 오름차순으로 정렬한다.

 

 

② 최소 간선들부터 선택하면서 순환이 발생하는지 확인하기(유니온-파인드 사용)

 

 

③ 모든 노드를 탐색하여 선택된 간선의 개수가 노드-1개라면 탐색 종료

 

 

3. 프림 알고리즘과 크루스칼 알고리즘 비교하기

프림 알고리즘은 정점 중심으로 동작하는 알고리즘이기에 그래프의 간선 수가 많을 때 효율적인 알고리즘인 반면에,

크루스칼 알고리즘은 간선 중심으로 동작하는 알고리즘이라서 그래프의 간선 수가 적을 때 유리한 알고리즘이다.

---

각 알고리즘으로 문제 풀어보기

1. 프림 알고리즘

⓪ 우선순위 큐 구현하기 : minHeap(최소힙)으로 구현

class MinHeap {
  constructor() {
    this.heap = []
  }

  push(node) {
    this.heap.push(node)
    this._heapifyUp()
  }

  pop() {
    if (this.size() === 1) return this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this._heapifyDown()
    return top
  }

  size() {
    return this.heap.length
  }

  _heapifyUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      if (this.heap[parentIndex].cost <= this.heap[index].cost) break
      ;[this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ]
      index = parentIndex
    }
  }

  _heapifyDown() {
    let index = 0
    const length = this.heap.length

    while (true) {
      const leftChildIndex = 2 * index + 1
      const rightChildIndex = 2 * index + 2
      let smallest = index

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = leftChildIndex
      }
      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = rightChildIndex
      }
      if (smallest === index) break
      ;[this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ]
      index = smallest
    }
  }
}

 

 

① 최소 비용 우선 탐색

• 상하좌우로 살펴보고 연결 가능한 모든 간선을 우선순위 큐에 넣음 : addEdges 함수

  // 0.간선 추가용 함수
  const addEdges = (x, y) => {
    for (const [dx, dy] of directions) {
      const nx = x + dx // 좌우
      const ny = y + dy // 상하
      // 방문하지 않은 칸 중에서 최소 비용을 가진 순으로 우선순위 큐에 삽입
      if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
        const cost = Math.abs(land[y][x] - land[ny][nx])
        pq.push({ x: nx, y: ny, cost: cost > height ? cost : 0 })
      }
    }
  }

 

• 가장 작은 비용의 간선을 선택하여 방문하지 않은 노드로 이동함 : while문으로 queue 탐색하기

 

 

② 방문 체크 후 갱신 : 방문한 노드는 다시 처리하지 않으며, 새로운 노드에서 연결 가능한 간선을 큐에 추가함

if (visited[y][x]) continue // 이미 방문한 노드라면 스킵
visited[y][x] = true // 방문 처리
totalCost += cost // 비용 추가
count++

 

 

③ 모든 노드를 연결할 때까지 반복 : MST가 완성될 때까지 위 과정을 반복하여 총 비용 계산

class MinHeap {
  constructor() {
    this.heap = []
  }

  push(node) {
    this.heap.push(node)
    this._heapifyUp()
  }

  pop() {
    if (this.size() === 1) return this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this._heapifyDown()
    return top
  }

  size() {
    return this.heap.length
  }

  _heapifyUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      if (this.heap[parentIndex].cost <= this.heap[index].cost) break
      ;[this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ]
      index = parentIndex
    }
  }

  _heapifyDown() {
    let index = 0
    const length = this.heap.length

    while (true) {
      const leftChildIndex = 2 * index + 1
      const rightChildIndex = 2 * index + 2
      let smallest = index

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = leftChildIndex
      }
      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = rightChildIndex
      }
      if (smallest === index) break
      ;[this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ]
      index = smallest
    }
  }
}

function solution(land, height) {
  // 0. 필요한 변수 정리
  const N = land.length
  // prettier-ignore
  const directions = [[0, 1],[1, 0],[0, -1],[-1, 0]] // 상하좌우 방향
  const visited = Array.from({ length: N }, () => Array(N).fill(false)) // 방문여부 배열 : 2차원 배열로 초기화
  const pq = new MinHeap() // 우선순위 큐 : Min-Heap 기반

  // 0.간선 추가용 함수
  const addEdges = (x, y) => {
    for (const [dx, dy] of directions) {
      const nx = x + dx // 좌우
      const ny = y + dy // 상하
      // 방문하지 않은 칸 중에서 최소 비용을 가진 순으로 우선순위 큐에 삽입
      if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
        const cost = Math.abs(land[y][x] - land[ny][nx])
        pq.push({ x: nx, y: ny, cost: cost > height ? cost : 0 })
      }
    }
  }

  let totalCost = 0 // 반환할 최소 비용
  let count = 0 // 방문한 칸 수
  pq.push({ x: 0, y: 0, cost: 0 }) // 시작점 추가

  while (pq.size() > 0) {
    // 우선순위 큐에서 최소 비용 간선을 선택
    const { x, y, cost } = pq.pop()

    if (visited[y][x]) continue // 이미 방문한 노드라면 스킵
    visited[y][x] = true // 방문 처리
    totalCost += cost // 비용 추가
    count++

    if (count === N * N) break // 모든 칸을 방문했으면 종료

    addEdges(x, y) // 현재 위치에서 새로운 간선 추가
  }

  return totalCost
}

 

 

 

2. 크루스칼 알고리즘

⓪ BFS로 구역 나누기 : 완전 탐색이므로 O(N²)

• bfs 함수 : queue를 사용하여 상하좌우로 이동하며 같은 구역으로 묶을 수 있는 그룹을 찾고 regionId(그룹 번호)를 할당하기
• 모든 칸에 대해 bfs 반복 실행 : 방문하지 않은 칸이 없을 때까지 bfs 함수 실행하기. 종료되면 regionId++

 

bfs 함수 

const bfs = (startX, startY, regionId) => {
    const queue = [[startX, startY]]
    visited[startY][startX] = true
    region[startY][startX] = regionId

    while (queue.length > 0) {
      const [x, y] = queue.shift()

      for (const [dx, dy] of directions) {
        const nx = x + dx
        const ny = y + dy

        if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
          const cost = Math.abs(land[y][x] - land[ny][nx])
          if (cost <= height) {
            // 같은 구역으로 묶을 수 있음
            visited[ny][nx] = true
            region[ny][nx] = regionId
            queue.push([nx, ny])
          }
        }
      }
    }
}

 

 

모든 칸에 대해 bfs 반복 실행

// 모든 칸에 대해 BFS로 구역 나누기
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) {
        regionCount++
        bfs(j, i, regionCount)
      }
    }
}

 

 

① 간선 리스트 생성하기 : 각 칸의 최대 4개의 간선을 탐색하므로 O(N²) + 간선 정렬은 O(ElogE) (E는 간선의 수)

• edges : {from, to, cost} 형태로 간선 저장해놓는 배열. cost를 기준으로 정렬된다.

// 간선 리스트 생성
const edges = []
for (let y = 0; y < N; y++) {
    for (let x = 0; x < N; x++) {
      for (const [dx, dy] of directions) {
        const nx = x + dx
        const ny = y + dy

        if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
          if (region[y][x] !== region[ny][nx]) {
            // 다른 구역 간의 간선만 추가
            const cost = Math.abs(land[y][x] - land[ny][nx])
            edges.push({
              from: region[y][x],
              to: region[ny][nx],
              cost,
            })
          }
        }
      }
    }
}


// 간선을 비용 기준으로 정렬
edges.sort((a, b) => a.cost - b.cost)

 

 

 

② 유니온-파인드 구현하기 : 경로 압축하기 (거의 상수시간의 수행)

• find(x) : 노드 x의 루트 찾기
• union(a, b) : 두 노드를 같은 집합으로 합침

// 유니온-파인드 구조체
const parent = Array(regionCount + 1)
  .fill(0)
  .map((_, index) => index)

const find = (x) => {
  if (parent[x] === x) return x
  return (parent[x] = find(parent[x])) // 경로 압축
}

const union = (a, b) => {
  const rootA = find(a)
  const rootB = find(b)
  if (rootA !== rootB) parent[rootB] = rootA
}

 

 

③ 크루스칼 알고리즘 사용하기

• 비용이 낮은 간선부터 선택하여 두 노드가 다른 집합에 속할 경우에만 연결함
• MST를 구성하고 총 비용 totalCost을 계산

// 크루스칼 알고리즘으로 최소 신장 트리 구성
let totalCost = 0
for (const { from, to, cost } of edges) {
  if (find(from) !== find(to)) {
    // 사이클이 생기지 않는 경우만 연결
    union(from, to)
    totalCost += cost
  }
}

---

3. 전체 코드

1. 프림 알고리즘 (O(N²logN²), N²개의 노드와 간선 처리)

class MinHeap {
  constructor() {
    this.heap = []
  }

  push(node) {
    this.heap.push(node)
    this._heapifyUp()
  }

  pop() {
    if (this.size() === 1) return this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = this.heap.pop()
    this._heapifyDown()
    return top
  }

  size() {
    return this.heap.length
  }

  _heapifyUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      if (this.heap[parentIndex].cost <= this.heap[index].cost) break
      ;[this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ]
      index = parentIndex
    }
  }

  _heapifyDown() {
    let index = 0
    const length = this.heap.length

    while (true) {
      const leftChildIndex = 2 * index + 1
      const rightChildIndex = 2 * index + 2
      let smallest = index

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = leftChildIndex
      }
      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex].cost < this.heap[smallest].cost
      ) {
        smallest = rightChildIndex
      }
      if (smallest === index) break
      ;[this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ]
      index = smallest
    }
  }
}

function solution(land, height) {
  // 0. 필요한 변수 정리
  const N = land.length
  // prettier-ignore
  const directions = [[0, 1],[1, 0],[0, -1],[-1, 0]] // 상하좌우 방향
  const visited = Array.from({ length: N }, () => Array(N).fill(false)) // 방문여부 배열 : 2차원 배열로 초기화
  const pq = new MinHeap() // 우선순위 큐 : Min-Heap 기반

  // 0.간선 추가용 함수
  const addEdges = (x, y) => {
    for (const [dx, dy] of directions) {
      const nx = x + dx // 좌우
      const ny = y + dy // 상하
      // 방문하지 않은 칸 중에서 최소 비용을 가진 순으로 우선순위 큐에 삽입
      if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
        const cost = Math.abs(land[y][x] - land[ny][nx])
        pq.push({ x: nx, y: ny, cost: cost > height ? cost : 0 })
      }
    }
  }

  let totalCost = 0 // 반환할 최소 비용
  let count = 0 // 방문한 칸 수
  pq.push({ x: 0, y: 0, cost: 0 }) // 시작점 추가

  while (pq.size() > 0) {
    // 우선순위 큐에서 최소 비용 간선을 선택
    const { x, y, cost } = pq.pop()

    if (visited[y][x]) continue // 이미 방문한 노드라면 스킵
    visited[y][x] = true // 방문 처리
    totalCost += cost // 비용 추가
    count++

    if (count === N * N) break // 모든 칸을 방문했으면 종료

    addEdges(x, y) // 현재 위치에서 새로운 간선 추가
  }

  return totalCost
}

 

 

2. 크루스칼 알고리즘 (O(N²logN²))

function solution(land, height) {
    const N = land.length;
    const directions = [
        [0, 1], [1, 0], [0, -1], [-1, 0]
    ]; // 상하좌우 방향
    const visited = Array.from({ length: N }, () => Array(N).fill(false));
    const region = Array.from({ length: N }, () => Array(N).fill(0));
    let regionCount = 0;

    // BFS로 구역 나누기
    const bfs = (startX, startY, regionId) => {
        const queue = [[startX, startY]];
        visited[startY][startX] = true;
        region[startY][startX] = regionId;

        while (queue.length > 0) {
            const [x, y] = queue.shift();

            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                    const cost = Math.abs(land[y][x] - land[ny][nx]);
                    if (cost <= height) { // 같은 구역으로 묶을 수 있음
                        visited[ny][nx] = true;
                        region[ny][nx] = regionId;
                        queue.push([nx, ny]);
                    }
                }
            }
        }
    };

    // 모든 칸에 대해 BFS로 구역 나누기
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (!visited[i][j]) {
                regionCount++;
                bfs(j, i, regionCount);
            }
        }
    }

    // 간선 리스트 생성
    const edges = [];
    for (let y = 0; y < N; y++) {
        for (let x = 0; x < N; x++) {
            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                    if (region[y][x] !== region[ny][nx]) { // 다른 구역 간의 간선만 추가
                        const cost = Math.abs(land[y][x] - land[ny][nx]);
                        edges.push({
                            from: region[y][x],
                            to: region[ny][nx],
                            cost
                        });
                    }
                }
            }
        }
    }

    // 간선을 비용 기준으로 정렬
    edges.sort((a, b) => a.cost - b.cost);

    // 유니온-파인드 구조체
    const parent = Array(regionCount + 1).fill(0).map((_, index) => index);

    const find = (x) => {
        if (parent[x] === x) return x;
        return parent[x] = find(parent[x]); // 경로 압축
    };

    const union = (a, b) => {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA !== rootB) parent[rootB] = rootA;
    };

    // 크루스칼 알고리즘으로 최소 신장 트리 구성
    let totalCost = 0;
    for (const { from, to, cost } of edges) {
        if (find(from) !== find(to)) { // 사이클이 생기지 않는 경우만 연결
            union(from, to);
            totalCost += cost;
        }
    }

    return totalCost;
}

 

 

출처

크루스칼 알고리즘 https://chanhuiseok.github.io/posts/algo-33/

프림 알고리즘 https://lu-coding.tistory.com/92