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

프로그래머스의 지형 이동(Lv4) 문제이다.

[ 문제풀이 ]

먼저 문제를 단계별로 나눠서 순서대로 차근차근 해결해보자.

본인은 이 문제를 크게 3가지 파트로 나누어 주었다.

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

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

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

이렇게 크게 3가지 파트로 나누어 보았다. 위의 3가지 파트를 하나씩 구체적으로 알아보자.

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

이 과정을 쉽게 생각해서 문제의 예시 설명에 있는 그림들 처럼 '같은 색깔로 지형들을 묶는 과정' 이라고 볼 수 있다.

이렇게 '사다리가 없이 이동이 가능한 지형들'을 다 묶고 나서는 그 지형들을 하나의 땅으로 판단할 것이다.

왜냐하면 이렇게 묶인 땅들은 사다리 설치 비용 없이 자유롭게 움직일 수 있기 때문이다.

이 부분을 너비우선탐색(BFS)를 이용해서 구현해 주었다. 탐색의 조건으로는 "현재 정점과, 탐색하려는 정점의 차이가 문제에서 제시한 사다리를 설치하지 않아도 되는 높이보다 작다면" 탐색을 진행해 주었다.

소스코드로 보면 다음과 같다.

void BFS(int a, int b, int Num, vector<vector<int>> MAP, int height)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = Num;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < MAP.size() && ny < MAP.size())
            {
                if (Visit[nx][ny] == 0 && abs(MAP[x][y] - MAP[nx][ny]) <= height)
                {
                    Visit[nx][ny] = Num;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}

위의 코드는 땅의 번호를 'Num' 으로 설정해주는 과정이다. 즉 ! 같은 색깔로 묶이게 되는 지형들(사다리 없이 지나다닐 수 있는 땅들)은 이제부터 'Num' 이라는 하나의 땅 처럼 표현할 것이다.

따라서, Visit배열을 bool형으로 선언해서 '방문을 했다, 안했다' 로 표시하지 않았고, int형으로 선언해서 해당 지형이 묶여있는 땅 덩어리의 번호로 설정해 주었다.

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

'같은 땅 덩어리로 묶이지 않은 지형들' 이라는 말은 곧 '사다리를 설치해야만 하는 지형들'을 의미한다. 문제의 예시 설명에 있는 그림에 빗대어 이야기해보면 '서로 다른 색깔의 지형들'을 의미한다.

즉 ! "서로 인접해 있는 지형들인데, 1번 과정에서 설정해준 Visit배열의 값이 서로 다르다면" 그 차이 만큼을 저장해 주었다.

이렇게 한다면 "같은 땅 덩어리들 간의 여러개의 값이 저장" 이 될 수도 있다.

무슨 말인지 그림을 통해서 알아보자. 아래의 그림은 문제에 주어진 입출력 2번에 대한 그림이다.

.

같은 색깔 끼리 묶인 지형들은 하나의 땅 덩어리로 표현될 수 있다.

.

위의 그림은 첫 번째 그림에서 해당 색깔이 의미하는 땅 덩어리의 번호를 적어본 것이다.

분홍색인 지형들은 모두 '1번' 땅덩어리에 속하는 지형들이고, 노랑색인 지형들은 모두 '2번' 땅 덩어리에 속하는 지형들이고,

파랑색 지형들은 모두 '3번'땅 덩어리에 속하는 지형들 이라는 것을 표시한 것이다.

그리고 위에서 말했듯이, "서로 인접하면서 서로 다른 땅 덩어리 번호를 가진 지형들" 간의 설치해야할 사다리의 높이를 구해보자.

.

아마 위의 그림처럼 빨강색 선을 그은 지형들이 "서로 인접하면서 서로 다른 땅 덩어리 번호를 가진 지형들" 에 속할 것이다.

그럼 위의 값들을 모두 저장해 주는 것이다. 저장을 할 때에는 { 설치해야 할 사다리의 비용 , 연결하는 2개의 땅 덩어리 번호 } 로

저장을 해 주었다.

예를 들어서 (0 , 0)에 있는 분홍색(10(1)) 로 표시된 지형과 (1, 0)에 있는 노랑색(2(2)) 로 표시된 지형을 저장할 때에는

{ 10 - 2 , { 1 , 2 } } 의 형태로 저장해 주었다.

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

위에서 구한 값들을 토대로 사다리의 설치 최소 비용을 구해보자. 본인은 이부분을 'MST(Minimal Spanning Tree)'를 이용해서 구현하였다. 위의 그림을 묶인 땅덩어리들을 노드로 생각해서 그래프를 그려보자면 다음과 같다.

.

이렇게 표현해볼 수 있다. 위에 적힌 { 8 , 10 }과 같은 값들은 "사다리를 설치할 수 있는 비용 후보들" 을 의미한다.

우리는 위의 상태에서, "모든 노드들을 다 탐색할 수 있으면서, 설치해야 하는 비용을 최소" 로 만들어야 한다. 즉 ! 최소스패닝트리를 구현하는 것과 동일한 연산이라고 볼 수 있다. 따라서 본인은 이 부분을 최소스패닝트리를 만드는 과정으로 구현하였다.

MST를 구현하는 방법은 일반적으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 아직 이 알고리즘들에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 크루스칼 알고리즘 알아보기(Click) ]

[ 프림 알고리즘 알아보기(Click) ]

본인은 크루스칼 알고리즘을 이용해서 구현하였다. 결과적으로 크루스칼 알고리즘을 통해서 MST를 구현하는데 드는 비용이 우리가 원하는 '사다리를 설치하는데 드는 최소비용' 이 된다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define MAX 305
using namespace std;
 
int Answer;
int Group_Cnt = 1;
int Visit[MAX][MAX];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
vector<int> Parent;
vector<pair<int, pair<int, int>>> Edge;
 
void BFS(int a, int b, int Num, vector<vector<int>> MAP, int height)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = Num;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < MAP.size() && ny < MAP.size())
            {
                if (Visit[nx][ny] == 0 && abs(MAP[x][y] - MAP[nx][ny]) <= height)
                {
                    Visit[nx][ny] = Num;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Make_Group(vector<vector<int>> land, int height)
{
    for (int i = 0; i < land.size(); i++)
    {
        for (int j = 0; j < land[i].size(); j++)
        {
            if (Visit[i][j] == 0) BFS(i, j, Group_Cnt++, land, height);
        }
    }
}
 
void Find_Group_Distance(vector<vector<int>> land, int height)
{
    for (int x = 0; x < land.size(); x++)
    {
        for (int y = 0; y < land.size(); y++)
        {
            for (int k = 0; k < 4; k++)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && ny >= 0 && nx < land.size() && ny < land.size())
                {
                    if (Visit[x][y] != Visit[nx][ny])
                    {
                        Edge.push_back(make_pair(abs(land[x][y] - land[nx][ny]), make_pair(Visit[x][y], Visit[nx][ny])));
                    }
                }
            }
        }
    }
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    return Parent[A] = Find_Parent(Parent[A]);
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    Parent[B] = A;
}
 
bool Same_Parent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    if (A == B) return true;
    return false;
}
 
void Kruskal()
{
    Parent.resize(Group_Cnt);
    sort(Edge.begin(), Edge.end());
    for (int i = 1; i < Group_Cnt; i++) Parent[i] = i;
    for (int i = 0; i < Edge.size(); i++)
    {
        int N1 = Edge[i].second.first;
        int N2 = Edge[i].second.second;
        int Cost = Edge[i].first;
        
        if(Same_Parent(N1, N2) == false)
        { 
            Union(N1, N2);
            Answer = Answer + Cost;
        }
    }
}
 
int solution(vector<vector<int>> land, int height)
{
    Make_Group(land, height);
    Find_Group_Distance(land, height);
    Kruskal();
 
    return Answer;
}