프로그래머스 : 지형 이동 c++

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

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

풀이

1. 일단 모든 지역을 사다리 없이 이동할 수 있는 구역으로 묶는다

2. 이제 크루스칼을 사용

 1) 하나의 지역은 노드

 2) 인접해있는 다른 지역으로 이동할때 드는 사다리 비용이 간선 길이

 3) 간선의 정보는 struct 로 저장 

   -> 섬 두개, 비용

 4) 비용에 따라 오름차순으로 정렬하고 유니온파인드 적용

   -> 연결되어 있지 않은 섬을 연결하는 다리인 경우에만 사용!

 5) answer에 다리 길이 더하기

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct tmp{
    int to,go;
    int value;
};

bool cmp(tmp a, tmp b)
{
    return a.value < b.value;
}

int d_r[4] ={1,-1,0,0};
int d_c[4] ={0,0,1,-1};
int visited[301][301]={0,};//0이면 속해있는 그룹 없는것
int answer = 0;
int n;
int parent[90000];

int getParent(int x)
{
    if(x == parent[x])
        return x;
    return parent[x] = getParent(parent[x]);
}
void connect(int x,int y)
{
    x = getParent(x);
    y = getParent(y);
    
    if(x<y)
        parent[y] =x;
    else
        parent[x] =y;
}

void labeling(int r, int c, int label,vector<vector<int>> land, int height)
{
    queue<pair<int,int> > q;
    q.push(make_pair(r,c));
    visited[r][c] = label;
    while(!q.empty())
    {
        r = q.front().first;
        c = q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int new_r = r + d_r[i];
            int new_c = c + d_c[i];
            if(new_r<0 || new_c<0 || new_r >=n | new_c >=n)
                continue;
            if(visited[new_r][new_c]!=0)
                continue;
            if( height < abs(land[r][c]-land[new_r][new_c]))
                continue;

            visited[new_r][new_c] =label;
            q.push(make_pair(new_r,new_c));
        }
        
    }
}

int solution(vector<vector<int>> land, int height) {
    n = land.size();
    int cnt=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(visited[i][j]==0)
            {
                visited[i][j]=cnt;
                labeling(i,j,cnt, land,height);
                cnt++;
            }
        }
    
    vector<tmp> bridges;
    vector<int> c;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            for(int k=0;k<4;k++)
            {
                int new_r = i+ d_r[k];
                int new_c = j + d_c[k];
                if(new_r <0 || new_c <0 || new_r >=n || new_c>=n)
                    continue;
                if(visited[new_r][new_c] == visited[i][j])
                    continue;
                
                tmp c;
                
                c.to = visited[new_r][new_c];
                c.go = visited[i][j];
                c.value = abs(land[new_r][new_c] - land[i][j]);
                bridges.push_back(c);
            }
        }
    
    for(int i=1;i<cnt;i++)
        parent[i] =i;
    
    sort(bridges.begin(),bridges.end(),cmp);
    
    for(int i=0;i<bridges.size();i++)
    {
        if(getParent(bridges[i].to) != getParent(bridges[i].go))
        {
            connect(bridges[i].to,bridges[i].go);
            answer += bridges[i].value;
        }
        
    }
    return answer;
}