[C/C++] Lv4 프로그래머스 - 지형 이동

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

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

- 접근법

문제와 주어진TC를 통한 예시를 보면, 각 배열에 담긴 값(높이)이 동,서,남,북 인접한 배열에 담긴 값과의 차이가 주어진 height 이하이면 cost없이 통할 수 있다. 그러나 height 보다 큰 인접한 곳은 '사다리'를 설치해야만 지나갈 수 있다.

 

결국 cost가 소모되는 것은 사다리를 통한 출입이며, height 이하의 인접한 곳은 언제든지 지나다닐 수 있다.따라서 먼저 cost 없이 지나갈 수 있는 곳을 모두 탐색하여 각 임의의 위치에서 cost가 소모되지 않고 지나갈 수 있는 곳들을 영역별로 나누어주자.

문제의 예시

이 문제에서는 아주 친절하게도 이렇게 가시성이 좋게 힌트까지 보여준다.

이렇게 색깔 별로 영역을 나누었다면 이 영역을 이제 사다리를 설치하여 '최소비용'으로 모든 영역을 갈 수 있게 하면 된다.

 

더 간단하게 생각하면 노란색 영역이 정점1, 파란색 영역이 정점2, 빨간색 영역이 정점3 으로 보면

정점1 에서 정점2로 가는 최소 사다리 설치비용 (5)

정점2 에서 정점3으로 가는 최소 사다리 설치비용 (10)

따라서 정점1,정점2,정점3을 모두 방문할수 있게 하는 최소 사다리 개수(간선)는 (정점개수3 - 1 = 2)개로 이루어진다.

 

즉, 모든 정점을 방문하게 하는 최소 비용 간선의 수(모든 정점의 개수 -1)을 구하는 문제(=MST 최소비용신장트리)이다.

 

총 정리하자면, 주어진 배열을 완전탐색하면서 영역을 나누어 정점화 시켜 얻은 데이터들을 edge list화 시킨 다음 MST로 풀면 되는 문제이다.

 

 

만약 최소 비용 신장트리(MST)를 처음 접한다면, 이 문제를 풀기전에 아래 유사문제를 먼저 푸는 것을 꼭 추천한다.

 

---

- 유사문제

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

코딩테스트 연습 - 섬 연결하기

최소비용신장트리 MST로 풀리는 기본적인 문제이다.

 

---

- 소스코드

#include <string>
#include <vector>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
vector<vector<int> > edge_list;
int board[302][302],main_map[302][302];
int parents[90010];
bool visit[301][301];
int p_x[4]={1,-1,0,0};
int p_y[4]={0,0,1,-1};
int N,count;
void init(vector<vector<int> > land) {
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            board[i][j]=land[i][j];
        }
    }
}
void DFS(int x,int y,int num_area,int height) {
    int next_x,next_y;
    main_map[x][y]=num_area;
    visit[x][y]=true;
    for(int i=0;i<4;i++) {
        next_x=x+p_x[i];
        next_y=y+p_y[i];
        if(next_x<0 || next_x==N || next_y<0 || next_y==N) continue;
        if(!visit[next_x][next_y] && abs(board[x][y]-board[next_x][next_y])<=height) {
            DFS(next_x,next_y,num_area,height);
        }
    }
    return;
}
void make_edge(int V) {
    int next_x,next_y;
    int A_area,B_area,temp;
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            A_area=main_map[i][j];
            for(int k=0;k<4;k++) {
                next_x=i+p_x[k];
                next_y=j+p_y[k];
                if(next_x<0 || next_x==N || next_y<0 || next_y==N) continue;
                B_area=main_map[next_x][next_y];
                if(A_area!=B_area) {
                    temp=abs(board[i][j]-board[next_x][next_y]);
                    edge_list.push_back({A_area,B_area,temp});
                }
            }
        }
    }
}
bool comp(vector<int> &A,vector<int> &B) {
    return A[2]<B[2];
}
int find_parents(int x) {
    if(x==parents[x]) return x;
    return parents[x]=find_parents(parents[x]);
}
void union_set(int x,int y) {
    x=find_parents(x);
    y=find_parents(y);
    parents[y]=x;
}
int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    int count=1,x,y;
    N=land.size();
    init(land);
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            if(!visit[i][j]) {
                DFS(i,j,count,height);
                count++;
            }
        }
    }
    make_edge(count);
    sort(edge_list.begin(),edge_list.end(),comp);
    //MST (Kruskal)
    for(int i=1;i<count;i++) {
        parents[i]=i;
    }
    for(int i=0;i<edge_list.size();i++) {
        x=edge_list[i][0];
        y=edge_list[i][1];
        if(find_parents(x)!=find_parents(y)) { // No cycle
            union_set(x,y);
            answer+=edge_list[i][2];
        }
    }
    return answer;
}