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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/62050

코딩테스트 연습 - 지형 이동

 

문제 확인

 

dp나 그래프 MST로 풀 수 있지만 크기가 작기 때문에 간단하게 bfs로도 풀 수 있습니다.

사다리 비용은 길이만큼 들기 때문에 여러개의 사다리를 놓는것에 대한 추가 비용이 없습니다. 따라서 최소 비용의 사다리를 선택 해 가면서 모든 지형을 방문하면 문제를 해결할 수 있습니다.

 

풀이

 

dfs를 통해서 풀 수 있을 것 같지만 재귀함수와 전역변수 사용에 시간초과가 날 것 같아서 bfs를 사용했습니다.

갈 수 있는 지형은 일반적인 큐를 사용하고 사다리를 놓아야 갈 수 있는 위치는 우선순위 큐를 사용해 가장 적은 비용의 사다리를 선택할 수 있도록 하였습니다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[] = { 1, -1, 0, 0 },
dy[] = { 0, 0, 1, -1 };
typedef struct point {
    int x, y, cost;
}point;
struct comp {
    bool operator()(point a, point b) { return a.cost > b.cost; }
};
int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    int cnt = 0, N = land.size();
    int cx, cy;
    int visited[300][300] = { 0 };
    queue<pair<int, int>> que; //갈 수 있는 위치들 기록
    priority_queue<point, vector<point>, comp> let; //우선순위 큐를 통해 가장 짧은 사다리 선택 할 수 있도록 함
    que.push({ 0, 0 });
    while (cnt < N*N) {
        if (que.empty()) {//더이상 사다리 없이 갈 수 있는 지형이 없다면 사다리 추가
            auto t = let.top();
            let.pop();
            cx = t.x; cy = t.y;
            if (visited[cx][cy])continue;
            answer += t.cost;
        }
        else {//다음 위치 이동
            auto t = que.front();
            que.pop();
            cx = t.first; cy = t.second;
            if (visited[cx][cy])continue;
        }
        cnt++;
        visited[cx][cy] = 1;
        for (int d = 0; d < 4; d++) {//갈 수 있는 위치 기록
            int nx = cx + dx[d], ny = cy + dy[d];
            if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                if (visited[nx][ny]) continue;
                int cost = abs(land[cx][cy] - land[nx][ny]);
                if (cost <= height) { //사다리 없이
                    que.push({ nx, ny });
                }
                else {//사다리 필요
                    let.push(point{ nx, ny, cost });
                }
            }
        }
    }
    return answer;
}
int main() {
    vector<vector<int>> board = { {10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1} };
    cout << solution(board, 1);
}
/*
{{10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1}}
{{1, 4, 8, 10}, {5, 5, 5, 5}, {10, 10, 10, 10}, {10, 10, 10, 20}}
우선순위 큐 사용해서 사다리를 둘 자리 선정, 사다리 없이 갈 수 있는 위치는 일반 큐 사용
*/