programmers [C++] : 지형 이동

programmers.co.kr/learn/courses/30/lessons/62050#

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

문제 설명

---

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

 

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

 

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

 

접근 방법

---

최단 거리를 구하기 위해서 Kruskal 알고리즘을 사용했습니다. 그 전에 bfs를 통해서 사다리 없이 이동할 수 있는 구역을 분류하고 최단거리 알고리즘을 적용했습니다.

 

코드

---

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int visit[305][305];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
int group_cnt=1;
vector<int>parent;
vector<pair<int,pair<int,int> > >edge;
int answer=0;

// bool inside(int a,int b,vector<vector<int>> land){
//     return ();
// }
// void print(vector<vector<int>> land){
//     for(int i=0;i<land.size();i++){
//         for(int j=0;j<land.size();j++){
//             cout<<visit[i][j]<<" ";
//         }
//         cout<<"\n";
//     }
// }
void distance(vector<vector<int>> land){
    int i,j;
    for(i=0;i<land.size();i++){
        for(j=0;j<land.size();j++){
            for(int k=0;k<4;k++){
                int ny=i+dy[k];
                int nx=j+dx[k];
                if((ny>=0&&nx>=0)&&(ny<land.size()&&nx<land.size())){
                    if(visit[i][j] != visit[ny][nx]){
                        edge.push_back(make_pair(abs(land[i][j]-land[ny][nx]),make_pair(visit[i][j],visit[ny][nx])));
                    }
                }
            }
        }
    }
}
void bfs(int y, int x,int num, vector<vector<int>> land,int h){
    queue<pair<int,int> >q;
    q.push(make_pair(y,x));
    visit[y][x]=num;
    while(!q.empty()){
        int cury=q.front().first;
        int curx=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int ny=cury+dy[i];
            int nx=curx+dx[i];
            if((ny>=0&&nx>=0)&&(ny<land.size()&&nx<land.size())){
                if(visit[ny][nx]==0&&abs(land[cury][curx]-land[ny][nx])<=h){
                    q.push(make_pair(ny,nx));
                    visit[ny][nx]=num;
                }
            }
        }
    }

}
int find_parent(int a){
    if(parent[a]==a)return a;
    return parent[a]=find_parent(parent[a]);
}
bool same_parent(int n1,int n2){
    n1=find_parent(n1);
    n2=find_parent(n2);
    if(n1==n2) return true;
    return false;
}
void Union(int n1,int n2){
    n1=find_parent(n1);
    n2=find_parent(n2);
    parent[n2]=n1;
}
void kruskal(){
    parent.resize(group_cnt);
    sort(edge.begin(),edge.end());
    for(int i=1;i<group_cnt;i++){
        parent[i]=i;
    }
    for(int i=0;i<edge.size();i++){
        int idx1=edge[i].second.first;
        int idx2=edge[i].second.second;
        int cost=edge[i].first;
        if(!same_parent(idx1,idx2)){
            Union(idx1,idx2);
            answer+=cost;
        }
    }
}
int solution(vector<vector<int>> land, int height) {
    
    for (int i = 0; i < land.size(); i++){
        for (int j = 0; j < land[i].size(); j++){
            if (visit[i][j] == 0) bfs(i,j,group_cnt++,land, height);
        }
    }
    distance(land);
    kruskal();
    //print(land);
    return answer;  
}

funny algorithm 0_<