[프로그래머스] 지형 이동 (Summer/Winter Coding 2019)

문제 링크

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

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

 

풀이

예제 설명을 색깔별로 친절하게 그려준 게 아마 큰 힌트가 되지 않을까 싶습니다.

 

1) 사다리를 쓰지 않고 이동할 수 있는 정점별로 그룹을 만들어줍니다. BFS, DFS 상관없습니다.

2) 위 그룹핑을 바탕으로 그래프를 재구성할 수 있습니다. 각 그룹을 정점으로, 그룹과 그룹 사이 사다리의 설치 비용을 간선으로 생각합시다.

3) 모든 그룹을 방문하되, 그 코스트의 합이 최소가 되어야 하므로 최소 스패닝 트리를 만들어주면 됩니다.

 

구현)

저 같은 경우는 크루스칼을 이용했습니다. 2번 과정에서 각 정점마다 4방향을 모두 보고 그룹이 다르면 그만큼의 코스트를 간선으로 추가해주었습니다. (line 58 ~ 69)

그룹의 최대 개수는 $N^{2}$개이고, 각 그룹마다 4개씩 간선이 생길 수 있으므로 간선의 총개수는 $4\cdot N^{2}$개입니다. 이는 충분히 가능한 복잡도입니다.

 

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;

int group[333][333];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int gnum, n, h;
int par[111'111];

int find(int x){
    if(par[x] == -1) return x;
    return par[x] = find(par[x]);
}
bool isValid(int x, int y){
    return 0 <= x && x < n && 0 <= y && y < n;
}
void dfs(vvi &land, int x, int y, int g){
    if(group[x][y]) return;
    group[x][y] = g;
    
    for(int k=0 ;k<4; k++){
		int nx = x + dx[k], ny = y+dy[k];
        
        if(isValid(nx, ny) && abs(land[nx][ny] - land[x][y]) <= h)
            dfs(land, nx, ny, g);
    }
}
struct Edge {
    int u, v, c;
    Edge(int u, int v, int c):u(u), v(v), c(c){}
};
int solution(vector<vector<int>> land, int height) {
    n = land.size();
    h = height;
    for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(!group[i][j]) dfs(land, i, j, ++gnum);
        }
    }
    vector<Edge> edges;
    for(int i=0; i<n ;i++){
		for(int j=0; j<n; j++){
            int u = group[i][j];
			for(int k=0; k<4; k++){
                int nx = i+dx[k], ny = j+dy[k];
                if(!isValid(nx, ny)) continue;
                int v = group[nx][ny];
                if(u == v) continue;
                int val1 = land[i][j], val2 = land[nx][ny];
                edges.emplace_back(u, v, abs(val1 - val2));
            }
        }
    }
    sort(all(edges), [&](const auto &a, const auto &b){
		return a.c < b.c;
    });
	memset(par, -1, sizeof(par));
    int ans = 0;
    for(auto &e: edges){
        auto [u, v, c] = e;
        u = find(u);
        v = find(v);
        if(u == v) continue;
        par[u] = v;
        ans += c;
    }
    
    return ans;
}