프로그래머스 문제 - 지형이동

프로그래머스 지형이동 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

최대 300 X 300크기의 정사각 격자 형태의 지형이 있음.
각 격자칸에는 높이를 나타내는 숫자가 적혀 있음.
지형의 아무 칸에서 시작하여 상,하,좌,우로 움직여 모든 칸을 방문해야함.
추가적으로 높이 값이 주어지는데 이 값 이하의 높이만 사다리 없이 방문할 수 있으며(height <= 높이일 경우 사다리 사용X) 그 이상의 높이는 사다리를 사용해야만 갈 수 있음.
사다리를 사용한 높이 1당 1의 비용이 들음.
이 때 최대한 적은 비용이 들도록 사다리를 사용하도록 해야함(출력값 -> 최소한의 비용 값)

최소한의 값 구하기, 맵을 통한 탐색, 지형 간의 사다리 설치 방법이 중요해보입니다.

문제 풀이

일단 여러 지형으로 나뉘어있기 때문에 사다리 없이 다닐 수 있는 지형을 알아내야 합니다.
2차원 배열에 각 지역의 값들이 들어가있기 때문에 깊이우선탐색(DFS)와 넓이우선탐색(BFS) 둘 중 하나를 사용해야 합니다.
이번에는 DFS를 사용하여 맵의 지형을 알아내었습니다.

//지형 탐색을 위한 dfs
void checkLand(int x, int y, int height, int level)
{
    checkMap[x][y] = level;
    for(int i = 0; i < 4; i++)
    {
        if(x+dx[i] >= 0 && y+dy[i] >= 0 && x+dx[i] < mapSize && y+dy[i] < mapSize)
        {
            int distance = abs(map[x][y] - map[x+dx[i]][y+dy[i]]);
            if(checkMap[x+dx[i]][y+dy[i]] == 0 && distance <= height)
            {
                checkLand(x+dx[i], y+dy[i], height, level);
            }
        }
    }
}

이후 계산한 지형을 사용하여 사다리를 설치할 수 있는 장소를 찾아야합니다.
계산된 지형의 상하좌우를 검색하여 자신의 지형과 다른 곳을 찾아서 (사다리 비용, 연결이 시작될 지형, 연결이 이루어질 지형) 3가지를 배열에 저장해줍니다.
이미 찾은 위치의 지형은 중복 연결을 막기 위해 -1로 바꿔줍니다.

//4방향을 체크하여 다른 지형이 있을 경우 사다리를 넣을 수 있다고 판단하여 배열에 넣어줌
void checkLadder(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
        if(x+dx[i] >= 0 && y+dy[i] >= 0 && x+dx[i] < mapSize && y+dy[i] < mapSize &&
           checkMap[x][y] != -1 && checkMap[x+dx[i]][y+dy[i]] != -1)
        {
            if(checkMap[x][y] != checkMap[x+dx[i]][y+dy[i]])
            {
                int distance = abs(map[x][y] - map[x+dx[i]][y+dy[i]]);
                ladder l;
                l.value = distance;
                l.startLand = checkMap[x][y];
                l.endLand = checkMap[x+dx[i]][y+dy[i]];
                checkLadderGroup.push_back(l);
            }
        }
    }
    checkMap[x][y] = -1;
}

최소값으로 연결된 사다리들의 합을 찾기 위하여 계산된 사다리들의 비용을 기준으로 정렬해줍니다.
그러기 위해서는 두 지형이 한개의 사다리로만 연결이 되어야하며 연결된 지형들은 하나의 영역으로 간주시켜야 합니다.
그러기 위해 union find를 사용해 이미 연결된 지형들을 같은 그룹넘버로 합쳐줌으로서 계산할 때 하나의 영역으로 간주시카도록 할 수 있습니다.

//union find를 위한 함수들
int findParent(int u)
{
    if(u == parent[u])  return u;
    return findParent(parent[u]);
}

void unionParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    a < b ? parent[b] = a : parent[a] = b;
}
//union find를 통한 비교
bool compareParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    return a == b;
}

사다리의 수는 정해진 지형의 그룹 수 - 1 만큼의 수를 가지게 됩니다.

//union find를 사용하여 연결된 지형들을 체크하며 값들을 순서대로 더해줌
    //지형 수-1만큼 더하면 사다리를 전부 찾았다는 뜻이므로 멈춤
    for(int i = 0; i < checkLadderGroup.size(); i++)
    {
        if(!compareParent(checkLadderGroup[i].startLand, checkLadderGroup[i].endLand))
        {
            answer += checkLadderGroup[i].value;
            unionParent(checkLadderGroup[i].startLand, checkLadderGroup[i].endLand);
            cnt++;
        }
        if(cnt == landCount-1)
        {
            break;
        }
    }

전체 코드

여러 가지 함수들의 사용하였기 때문에 코드가 생각보다 길어졌습니다.
맵을 계산하는것을 난이도가 낮았지만 사다리들의 비용 계산과 어떤 식으로 사다리를 연결시켜야하는가 생각하는 것이 힘들었습니다.

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//지형 간 연결할 수 있는 사다리 비용과 두 지형의 값 저장
struct ladder{
    int value;
    int startLand;
    int endLand;
};

vector<vector<int>> map;
vector<vector<int>> checkMap;
vector<ladder> checkLadderGroup;
//dfs의 4방향 값
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int mapSize;
int parent[90000];

//sort를 위한 compare함수
bool compare(ladder a, ladder b) { return a.value < b.value; }

//union find를 위한 함수들
int findParent(int u)
{
    if(u == parent[u])  return u;
    return findParent(parent[u]);
}

void unionParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    a < b ? parent[b] = a : parent[a] = b;
}
//union find를 통한 비교
bool compareParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    return a == b;
}
//지형 탐색을 위한 dfs
void checkLand(int x, int y, int height, int level)
{
    checkMap[x][y] = level;
    for(int i = 0; i < 4; i++)
    {
        if(x+dx[i] >= 0 && y+dy[i] >= 0 && x+dx[i] < mapSize && y+dy[i] < mapSize)
        {
            int distance = abs(map[x][y] - map[x+dx[i]][y+dy[i]]);
            if(checkMap[x+dx[i]][y+dy[i]] == 0 && distance <= height)
            {
                checkLand(x+dx[i], y+dy[i], height, level);
            }
        }
    }
}
//4방향을 체크하여 다른 지형이 있을 경우 사다리를 넣을 수 있다고 판단하여 배열에 넣어줌
void checkLadder(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
        if(x+dx[i] >= 0 && y+dy[i] >= 0 && x+dx[i] < mapSize && y+dy[i] < mapSize &&
           checkMap[x][y] != -1 && checkMap[x+dx[i]][y+dy[i]] != -1)
        {
            if(checkMap[x][y] != checkMap[x+dx[i]][y+dy[i]])
            {
                int distance = abs(map[x][y] - map[x+dx[i]][y+dy[i]]);
                ladder l;
                l.value = distance;
                l.startLand = checkMap[x][y];
                l.endLand = checkMap[x+dx[i]][y+dy[i]];
                checkLadderGroup.push_back(l);
            }
        }
    }
    checkMap[x][y] = -1;
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    int landCount = 0;
    map = land;
    mapSize = land.size();
    
    //지형 계산을 위한 checkMap을 초기화시켜줌
    vector<int> t(mapSize, 0);
    for(int i = 0; i < mapSize; i++)
    {
        checkMap.push_back(t);
    }
    
    //dfs를 통해 사다리 없이 다닐 수 있는 지형을 checkMap에 기록함
    for(int i = 0; i < mapSize; i++)
    {
        for(int j = 0; j < mapSize; j++)
        {
            if(checkMap[i][j] == 0)
            {
                landCount++;
                checkLand(i, j, height, landCount);
            }
        }
    }
    //union find 계산를 위한 배열 초기화
    for(int i = 0; i < landCount; i++)
    {
        parent[i] = i;
    }
    
    //지형 간의 사다리를 놓는 경우의 수를 checkLadderGroup에 넣어줌
    for(int i = 0; i < mapSize; i++)
    {
        for(int j = 0; j < mapSize; j++)
        {
            if(checkMap[i][j] != 0)
            {
                checkLadder(i, j);
            }
        }
    }
    
    //비용을 기준으로 오름차순 정렬
    sort(checkLadderGroup.begin(), checkLadderGroup.end(), compare);
    
    int cnt = 0;
    //union find를 사용하여 연결된 지형들을 체크하며 값들을 순서대로 더해줌
    //지형 수-1만큼 더하면 사다리를 전부 찾았다는 뜻이므로 멈춤
    for(int i = 0; i < checkLadderGroup.size(); i++)
    {
        if(!compareParent(checkLadderGroup[i].startLand, checkLadderGroup[i].endLand))
        {
            answer += checkLadderGroup[i].value;
            unionParent(checkLadderGroup[i].startLand, checkLadderGroup[i].endLand);
            cnt++;
        }
        if(cnt == landCount-1)
        {
            break;
        }
    }

    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/62050