[프로그래머스] 지형 이동

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

해당 문제는 크게 3단계로 풀이된다.

1. 사다리 설치가 필요없는 지형들 그룹화
2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장
3. 저장된 최소 비용들로 MST 생성

1. 사다리 설치가 필요없는 지형들 그룹화
DFS 혹은 BFS를 사용하여 사다리가 필요없이 이동가능한 지형들을 하나의 그룹으로 표시한다. 아래의 코드에서는 방문 여부를 체크하는 visited배열을 int형으로 선언하여 방문 여부의 체크와 그룹 표시를 같이 진행하였다.

2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장
visited배열에 그룹을 구분하였다면 각 그룹별 이동하는 최소 비용을 구하여 edges<pair<int, pair<int, int>>에 저장한다.

3. 저장된 최소 비용들로 MST생성
MST는 Kruskal 알고리즘을 사용하여 생성하여 답을 계산하였다.

코드

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

int n, h, num, ans = INT_MAX;
vector<int> parent, size;
vector<vector<int>> visited;
vector<bool> chk;
vector<pair<int, pair<int, int>>> edges;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

int find(int u) {
    if (u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);

    if (u == v) return;
    if (size[u] < size[v]) swap(u, v);
    parent[v] = u;
    if (size[u] == size[v]) size[u]++;
}

int kruskal() {
    int cnt = 1;
    int ret = 0;    

    // 최소 비용의 사다리부터 설치할 수 있도록 정렬
    sort(edges.begin(), edges.end());

    for (int i = 0; i < edges.size(); i++) {
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        if (find(a) == find(b)) continue;
        merge(a, b);
        ret += cost;
        // 모든 그룹이 연결된 경우 반복문을 중지
        if (++cnt == num) break;
    }
    return ret;
}

// 그룹 간 이동할 때 필요한 비용을 저장
void getCost(vector<vector<int>>& land) {
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[y][x] == visited[ny][nx]) continue;
                // 사다리를 설치해야하는 경우를 모두 저장
                edges.push_back({ abs(land[y][x] - land[ny][nx]), {visited[y][x], visited[ny][nx]} });
            }
        }
    }
}

// BFS를 해서 그룹을 분류
void bfs(int x, int y, int num, vector<vector<int>>& land) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[y][x] = num;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (visited[ny][nx] || abs(land[cur.second][cur.first] - land[ny][nx]) > h) continue;
            visited[ny][nx] = num;
            q.push({ nx, ny });
        }
    }
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    n = land.size();
    h = height;

    // 그룹 분류
    visited = vector<vector<int>>(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!visited[i][j]) bfs(j, i, ++num, land);

    chk = vector<bool>(num, false);
    parent = vector<int>(num + 1);
    size = vector<int>(num + 1, 0);

    // 사다리를 놓아야 하는 경우에 필요한 비용을 저장
    getCost(land);

    for (int i = 1; i <= num; i++) parent[i] = i;

    // Kruskal 알고리즘을 통해 MST생성 및 결과 반환
    answer = kruskal();
    return answer;
}