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

문제 설명

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 이하인 자연수입니다.

---

입출력 예

land	height	result
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]	3	15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

입출력 예 설명

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

풀이)

bfs와 MST의 kruskal알고리즘을 이용해서 푼 문제이다.

풀이과정은 이러하다.

bfs과정

1. bfs를 통해 구역을 나눠준다. (한 구역은 높이차이가 height보다 적어서 마음껏 이동할 수 있는 구역을 뜻한다.)

 (즉 사다리 없이 이동할 수 있는 지형들끼리 묶은 것.)

2. 구역을 나눠줄 때, 다른 구역과 만난다면 현재 있는 구역과 다른구역의 번호와 높이차를 저장해준다.

MST과정

3. 모든 구역을 나눴으면 구역들끼리의 연결 저장해둔 배열을 높이차 순으로 정렬해준다. -> kruskal 알고리즘

4. 낮은 높이차를 가진 구역들끼리 연결해준다. -> find&union 작업

5. 모든 구역이 연결되었으면 종료

-참고-

처음에 bfs가 아닌 dfs로 구역을 나눠줬었는데, 테스트 케이스 24에서 시간초과가 생겼다.

그래서 bfs로 바꿨더니 통과했다.

코드)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> visited; // 방문여부
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int N, l_cnt =0; // 맵사이즈, 같은 범위 개수
vector<int> parent; 
vector <pair<int,pair<int,int>>> temp; // 간선 가중치 저장

void bfs(int y,int x,vector<vector<int>> land,int height){
    visited[y][x] = l_cnt;
    queue<pair<int,int>> qu;
    qu.push({y,x});
    while(!qu.empty()){
        int y = qu.front().first;
        int x = qu.front().second;
         qu.pop();
         for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >=0 && ny < N && nx >=0 && nx <N){

                int dist = abs(land[ny][nx] - land[y][x]);

                if(visited[ny][nx] >= 0){//같은 구역인데 이미 방문 or 다른 구역일때
                    if(visited[ny][nx] != l_cnt) temp.push_back({dist,{l_cnt,visited[ny][nx]}});
                    continue;
                }

                 if(dist > height) continue;//높이차가 많이 날때
                visited[ny][nx] = l_cnt;
                qu.push({ny,nx});
            }
        }
    }
}

int Find(int x){
    if(parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}
void Union(int x,int y){
    parent[y] = x;
    return;
}
int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    N = land.size();
    visited.resize(N,vector<int>(N,-1));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(visited[i][j] >= 0) continue;
            visited[i][j] = l_cnt;
            bfs(i,j,land,height);
            l_cnt++;
        }
    }

    sort(temp.begin(),temp.end());

    for(int i=0;i<l_cnt;i++) parent.push_back(i);

    for(int i=0;i<temp.size();i++){
        int a = Find(temp[i].second.first);
        int b = Find(temp[i].second.second);

        if(a != b){
            Union(a,b);
            answer += temp[i].first;
        }
    }
    return answer;
}