[PCCP] Lv4: 지형 이동(62050) 해설

문제

- 문제 링크: 지형 이동

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: land의 한 변의 길이

- 각 지점을 방문하는데 필요힌 시간 복잡도: O(N^2)

- 우선순위 큐를 활용해 너비 우선 탐색을 진행하므로 최종 시간 복잡도는 O(N^2 * log(N^2))

import java.util.PriorityQueue;

class Solution {
    private static class Node {
        int i, j, cost;
        public Node(int i, int j, int cost) {
            this.i = i;
            this.j = j;
            this.cost = cost;
        }
    }
    
    public int solution(int[][] land, int height) {
        int answer = 0;
        int n = land.length;
        // 주변 노드 탐색을 위해 di, dj
        int[] di = {-1, 0, 1, 0};
        int[] dj = {0, 1, 0, -1};
        boolean[][] visited = new boolean[n][n];
        
        // 시작 노드 추가
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
        pq.add(new Node(0, 0, 0));
        
        // BFS + 우선순위 큐로 다음 노드 관리
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            // 아직 방문하지 않은 경로만 탐색
            if (visited[now.i][now.j])
                continue;
            
            visited[now.i][now.j] = true;
            // 현재까지 비용을 합산
            answer += now.cost;
            
            for (int i = 0; i < 4; ++i) {
                int ni = now.i + di[i];
                int nj = now.j + dj[i];
                
                // 유효한 인덱스가 아닐 경우
                if (!(0 <= ni && ni < n && 0 <= nj && nj < n))
                    continue;
                    
                int tempCost = Math.abs(land[now.i][now.j] - land[ni][nj]);
                // 입력으로 주어진 height보다 높이차가 큰 경우
                int newCost = tempCost > height ? tempCost : 0;
                // 다음 경로를 add
                pq.add(new Node(ni, nj, newCost));
            }
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: land의 한 변의 길이

- 각 지점을 방문하는데에 필요한 시간 복잡도: O(N^2)

- 우선순위 큐를 활용해 너비 우선 탐색을 진행하므로 최종 시간 복잡도: O((N^2)*log(N^2)) 

from heapq import heappush, heappop

def solution(land, height):
    answer = 0
    n = len(land)
    # 주변 노드 탐색을 위한 di, dj
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]
    visited = [[False] * n for _ in range(n)]
    
    # 시작 노드 추가
    q = []
    heappush(q, [0,0,0]) # [비용, i, j]
    
    # BFS + 우선순위 큐로 다음 노드 관리
    while q:
        cost, i, j = heappop(q)
        # 아직 방문하지 않은 경로만 탐색
        if not visited[i][j]:
            visited[i][j] = True
            # 현재까지 비용을 합산
            answer += cost
            for d in range(4):
                ni, nj = i + di[d], j + dj[d]
                # 유효한 인덱스일 경우
                if 0 <= ni < n and 0 <= nj < n:
                    temp_cost = abs(land[i][j] - land[ni][nj])
                    # 입력으로 주어진 height보다 높이차가 큰 경우
                    if temp_cost > height:
                        new_cost = temp_cost
                    else:
                        new_cost = 0
                    # 다음 경로를 푸시
                    heappush(q, [new_cost, ni, nj])
                    
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: land의 한 변의 길이

- 각 지점을 방문하는데 필요한 시간 복잡도: O(N^2)

- 우선순위 큐를 활용해 너비 우선 탐색을 진행: O(N^2 * log(N^2))

class MinHeap {
    constructor() {
        this.items = [];
    }
    
    size() {
        return this.items.length;
    }
    
    push(item) {
        this.items.push(item);
        this.bubbleUp();
    }
    
    pop() {
        if (this.size() === 0) {
            return null;
        }
        
        const min = this.items[0];
        this.items[0] = this.items[this.size() - 1];
        this.items.pop();
        this.bubbleDown();
        return min;
    }
    
    swap(a, b) {
        [this.items[a], this.items[b]] = [this.items[b], this.items[a]];
    }
    
    bubbleUp() {
        let index = this.size() - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.items[parentIndex][0] <= this.items[index][0]) {
                break;
            }
            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    
    bubbleDown() {
        let index = 0;
        while (index * 2 + 1 < this.size()) {
            let leftChild = index * 2 + 1;
            let rightChild = index * 2 + 2;
            let smallerChild = 
                rightChild < this.size() && 
                this.items[rightChild][0] < this.items[leftChild][0]
                ? rightChild
                : leftChild;
            
            if (this.items[index][0] <= this.items[smallerChild][0]) {
                break;
            }
            
            this.swap(index, smallerChild);
            index = smallerChild;
        }
    }
}

function solution(land, height) {
    let answer = 0;
    const n = land.length;
    
    // 주변 노드 탐색을 위한 di, dj
    const di = [-1, 0, 1, 0];
    const dj = [0, 1, 0, -1];
    const visited = Array.from(Array(n), () => Array(n).fill(false));

    // 시각 노드 추가
    const q = new MinHeap();
    
    q.push([0, 0, 0]); // [비용, i, j]
    
    // BFS + 우선 순위 큐로 다음 노드 관리
    while (q.size() > 0) {
        const [cost, i, j] = q.pop();
        // 아직 방문하지 않은 경로만 탐색
        if (!visited[i][j]) {
            visited[i][j] = true;
            // 현재까지 비용을 합산
            answer += cost;
            for (let d = 0; d < 4; ++d) {
                const ni = i + di[d];
                const nj = j + dj[d];
                // 유효한 인덱스일 경우
                if (0 <= ni && ni < n && 0 <= nj && nj < n) {
                    const tempCost = Math.abs(land[i][j] - land[ni][nj]);
                    // 입력으로 주어진 height보다 높이차가 큰 경우
                    const newCost = tempCost > height ? tempCost : 0;
                    // 다음 경로를 푸시
                    q.push([newCost, ni, nj]);
                }
            }
        }
    }

    return answer;
}

solution 2)

import

solution 3)

import