[프로그래머스] 지형이동 (C++)

1.문제

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

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

2.풀이

1. 사다리가 없이 이동이 가능한 지형끼리 묶기

2. 같은 땅덩어리로 묶이지 않은 지형들 간의 거리 구하기

3. 사다리의 설치 최소 비용 구하기

나는 1번을 dfs 알고리즘으로 구현하였다. (bfs 도 상관없음)

2번은 벡터를 구조체로 선언하여 (from , to, dist)로 저장을한 뒤 dist (높이 차이)가 가장 작은 순서대로 sorting하였다.

 

3번은 크루스칼 알고리즘(MST) 을 적용해서 가장 적은 비용을 구한다.

 

크루스칼 알고리즘 ,,, 다시 한 번 정리해야겠다.

3.코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
/*
현재칸-이동칸 <= height
사다리 비용 = 높이차
모든 칸으로 이동 가능하도록 최소 설치 비용 return
*/

using namespace std;

int dir[4][2]= {{1,0}, {0,1}, {-1,0},{0,-1}};
int visit[301][301]={0};
int m[301][301];
int answer;

typedef struct Info{
    int from, to, dist;
}Info;

vector<Info> v;
int p[301*301]={0};

bool cmp(Info a, Info b){
    return a.dist<b.dist;
}

void dfs(int y, int x, vector<vector<int>> &land, int height, int idx){
    m[y][x] = idx;
    visit[y][x] = 1;
    
    for(int i=0; i<4; i++){
        int ny = y + dir[i][0];
        int nx = x + dir[i][1];
        if(ny<0 || ny>=land.size() || nx <0 || nx>=land[0].size() || visit[ny][nx])
            continue;
        
        int diff = abs(land[y][x]-land[ny][nx]);
        if(diff <= height){
            dfs(ny, nx, land, height, idx);
        }
    }
    return;
}

int find_parent(int a){
    if( a==p[a])
        return a;
    return p[a] = find_parent(p[a]);
}

void Union(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    p[b] = a;
    
}
void kruskal(int idx){
    for(int i=1; i<idx; i++){
        p[i] = i;
    }
    for(int i=0; i<v.size(); i++){
        int n1 = v[i].from;
        int n2 = v[i].to;
        int cost = v[i].dist;
        
        if(find_parent(n1) != find_parent(n2)){
            Union(n1, n2);
            answer += cost;
        }
    }
}
int solution(vector<vector<int>> land, int height) {
    answer = 0;
    int idx = 1;
    
    //칸 영역 구분
    for(int i=0; i<land.size(); i++){
        for(int j=0; j<land[0].size(); j++){
            if(!visit[i][j]){
                dfs(i, j, land, height, idx);
                ++idx;
            }
        }
    }
    //다른 그룹의 높이 차이 저장 : from,to,dist
    for(int y=0; y<land.size(); y++){
        for(int x=0; x<land[0].size(); x++){
            for(int i=0; i<4; i++){
                int ny = y + dir[i][0];
                int nx = x + dir[i][1];
                
                if(ny<0 || ny >= land.size() || nx<0 || nx>=land[0].size())
                    continue;
                if(m[y][x] == m[ny][nx])
                    continue;
                int from = m[y][x]; int to = m[ny][nx];
                v.push_back({from ,to, abs(land[y][x]-land[ny][nx])});
            }
        }
    }

    //높이 차 작은 순으로 정렬
    sort(v.begin(), v.end(), cmp);
    //크루스칼 알고리즘(MST)을 통해 사다리 설치 최소 비용 구하기
    kruskal(idx);
    
    return answer;
}

---

참고 : https://yabmoons.tistory.com/470 [얍문's Coding World..]