[프로그래머스 Lv4] : 지형 이동

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/62050

프로그래머스

모든 칸에 방문하기 위한 사다리 설치 비용의 최솟값을 리턴해주자.

 

풀이

모든 칸에서 상하좌우로 이동할 수 있으며 높이 차가 주어진 height 값보다 작거나 같으면 그냥 이동할 수 있지만 높이 차가 height 보다 크다면 높이 차이만큼의 비용을 내고 사다리를 설치해야한다.

 

각 칸을 정점으로 봤을 때, 모든 정점을 이어지도록 하는 길을 찾아야한다는 뜻이다. 임의의 칸을 기준으로 상하좌우 칸으로 간선이 이어져있다고 생각해보면, 높이차가 height 이하면 간선의 가중치가 0이고 height보다 크면 높이 차 만큼의 가중치가 붙는 것이다.

이때 간선의 가중치가 작은 것부터 차례차레 이동하면서 모든 정점을 방문하도록 하면 된다.

시작점은 어디든 상관없다고 했지만, 모든 칸을 이어야하기 때문에 사실 어디서 출발하든 상관이 없다.

나는 편의상 맨 왼쪽 맨 윗칸 (0, 0)을 시작점으로 설정해주었다.

 

(0,0)으로 시작해서 인접한 칸과의 간선을 우선순위 큐에 집어넣는다. 이때 정렬기준은 오름차순으로 해서 간선의 비용이 작은 것부터 꺼낼 수 있도록 한다.

이미 방문한 칸은 스킵해주고 방문하지 않은 칸이라면 상하좌우 인접한 칸과의 간선을 우선순위큐에 계속해서 넣어준다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
 
bool is_ok(pair<int,int> pos, const int& N){
    if(pos.first < 0 || pos.first >= N || pos.second < 0 || pos.second >= N)
        return false;
    return true;
}
 
int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    int N = land.size();
    bool visited[301][301];
    memset(visited,false,sizeof(visited));
    
    priority_queue<pair<int, pair<int,int>>> pq;
    pq.push({0, {0,0}});
    while(!pq.empty()){
        pair<int,int> now = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        if(visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        answer += cost;
        for(int i = 0; i<4; i++){
            pair<int,int> next = {now.first + dy[i], now.second + dx[i]};
            if(!is_ok(next, N))
                continue;
            int acost = 0;
            if(abs(land[now.first][now.second] - land[next.first][next.second]) > height)
                acost = abs(land[now.first][now.second] - land[next.first][next.second]);
            pq.push({-acost,next});
        }
    }
    
    return answer;
}

 

나는 BFS를 이용해서 모든 칸을 방문하는 것으로 했지만, 최소 스패닝 트리를 이용해서 모든 정점을 잇는 트리를 만들어도 될 것 같다.