프로그래머스[Lv.4] - 지형 이동

문제 설명

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

---

 

 

 

 

 

 

제한 사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

---

 

 

 

 

 

 

풀이

문제를 요약하면, 모든 칸을 방문하는 최소 비용을 구하는 것이다.

이때, 비용은 정해진 높이이상 차이가 나면 그 높이의 차이만큼 발생한다.

 

처음 문제를 풀 때는 비용 없이 이동할 수 있는 부분을 나눈 뒤, 구간간의 이동을 생각하려 했다.

물론 이렇게 풀어도 답을 구할 수는 있다.

하지만, 한 번 방문한 칸을 다시 방문할 수 있기 때문에 구간간의 이동 경로가 무수히 많아진다.

최대 300 x 300의 입력이기 때문에, 90,000개의 구간이 나올 수 있고 이를 순열로 이동 경로를 만들 수 있기 때문에 시간 복잡도를 장담할 수 없다.

 

즉, 다른 접근법이 필요하다.

문제를 간단히 요약해 보면 결국 최소 비용을 구하는 것이다.

결국 모든 칸을 이동할 때, 최소 비용을 우선하여 이동하면 모든 칸을 최소 비용으로 방문할 수 있다.

이게 가능한 이유는 한 번 방문한 칸을 다시 방문하여 이동할 수 있기 때문이다.

 

높이가 height 이상 차이 나지 않는 칸은 비용이 0이므로 우선적으로 방문할 것이고, 비용이 발생하는 칸에 방문하더라도 최소 비용으로 이동할 것이다.

이런 방식에 잘 어울리는 자료구조가 있다.

바로, priority_queue이다.

pq에 발생하는 비용을 통해 정렬하여 최소 비용을 골라올 수 있다.

struct cmp
{
    bool operator()(tuple<int,int,int>& a, tuple<int,int,int>& b)
    {
        return get<2>(a) > get<2>(b);
    }
};

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, cmp> pq;

N x N번의 칸에 방문하면 최소 비용을 반환하면 된다.

 

이때, 주의해야 할 점이 있다.

방문한 칸에 다시 방문할 수 있는 것은 맞지만, 방문한 칸에 다시 방문하여 새로운 이동 경로를 추가할 필요는 없다.

만약, 이 부분이 지켜지지 않는다면 더 많은 연산이 필요하다.

또한, 모든 칸에 방문했는지 여부를 판단하기 위해 방문한 칸의 횟수를 체크하도록 설계하였는데 이 로직이 깨질 수 있다.

따라서, 방문여부를 저장하여 이동 경로를 다시 추가하지 않도록 설계하였다.

do{
    auto current = pq.top();
    pq.pop();

    y = get<0>(current);
    x = get<1>(current);
    cost = get<2>(current);
}while(visited[y][x] && !pq.empty());

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <iostream>

using namespace std;

struct cmp
{
    bool operator()(tuple<int,int,int>& a, tuple<int,int,int>& b)
    {
        return get<2>(a) > get<2>(b);
    }
};

int Search(vector<vector<int>>& land, priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, cmp>& pq, int cnt, int height, vector<vector<bool>>& visited, int totalCost)
{
    int y;
    int x;
    int cost;
    
    do{
        auto current = pq.top();
        pq.pop();
        
        y = get<0>(current);
        x = get<1>(current);
        cost = get<2>(current);
    }while(visited[y][x] && !pq.empty());
    
    visited[y][x] = true;
    
    if(cnt == land.size() * land[0].size())
    {
        return totalCost + cost;
    }
    
    vector<int> dy = {-1, 0, 1, 0};
    vector<int> dx = {0, 1, 0, -1};
    
    for(int i = 0; i < 4; i++)
    {
        int newY = y + dy[i];
        int newX = x + dx[i];
        
        if(newY < 0 || newY >= land.size() || newX < 0 || newX >= land[0].size()) continue;
        if(visited[newY][newX]) continue;
        
        int addtive = abs(land[newY][newX] - land[y][x]) <= height ? 0 : abs(land[newY][newX] - land[y][x]);
        pq.push({newY, newX, addtive});
    }
    
    return Search(land, pq, cnt+1, height, visited, totalCost+cost);
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    
    vector<vector<bool>> visited(land.size(), vector<bool>(land[0].size(), false));
    
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, cmp> pq;
    pq.push({0,0,0});
    visited[0][0] = true;
    
    answer = Search(land, pq, 1, height, visited, 0);
        
    return answer;
}

---