[Programmers] 지형 이동

summer/winter coding(2019)

 

문제

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

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

 

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

 

---

 

해결 방법

사다리 없이 이동할 수 있는 구역끼리 묶어 나눈다.

서로 다른 구역의 차이 값을 확인하여 그 중 최솟값을 찾는다.

최소한 차이가 나는 위치에 사다리를 놓고, 두 구역을 연결한다.

위의 방법을 반복하여 최소한의 비용으로 사다리를 놓는 방법을 찾는다.

이는 크루스칼 알로리즘이다.

---

크루스칼 알고리즘

사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 만드는 최소 신장 트리를 말한다.

• 하나의 트리를 키워나가는 방식이 아닌, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 존재한다.
• 하나의 간선을 더할 때마다 두 개의 트리가 하나의 트리로 합쳐진다.

 

---

 

따라서, 아래와 같이 문제를 풀 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int count; //구역의 수
vector<vector<int>> group; //구역의 값을 저장한 배열

//구역을 나누어 group에 저장함
void    bfs(vector<vector<int>>& land, int& height, int x, int y, int num){
    int len = land.size();
    
	//좌
    if (x > 0 && !group[x - 1][y]){
        if (abs(land[x][y] - land[x - 1][y]) <= height) {
            group[x - 1][y] = num;
            bfs(land, height, x - 1, y, num);
        }
    }
	//아래
    if (y > 0 && !group[x][y - 1]){
        if (abs(land[x][y] - land[x][y - 1]) <= height) {
            group[x][y - 1] = num;
            bfs(land, height, x, y - 1, num);
        }
    }
	//우
    if (x < len - 1 && !group[x + 1][y]){
        if (abs(land[x][y] - land[x + 1][y]) <= height) {
            group[x + 1][y] = num;
            bfs(land, height, x + 1, y, num);            
        }
    }
	//위
    if (y < len - 1 && !group[x][y + 1]){
        if (abs(land[x][y] - land[x][y + 1]) <= height) {
            group[x][y + 1] = num;
            bfs(land, height, x, y + 1, num);            
        }
    }
}

//구역을 나누어 저장함.
void    makeGroup(vector<vector<int>>& land, int& height){
    int num = 1;
    
    for (int i = 0; i < land.size(); i++){
        for (int j = 0; j < land.size(); j++){
            if (group[i][j] == 0) {
                group[i][j] = num;
                bfs(land, height, i, j, num);
                num++;
            }
        }
    }
	//구역의 개수
    count = num - 1;
}

//최소값 찾기
void    checkGap(vector<vector<int>>& land, int& minGap, int& from, int& to, int i, int j, int x, int y){
    if (minGap == 0 || minGap > abs(land[i][j] - land[x][y])){
        minGap = abs(land[i][j] - land[x][y]);
        from = group[i][j];
        to = group[x][y];
    }
}

//서로 다른 구역을 연결한 후, 하나의 값으로 바꾸어 저장함
void    arrangeGroup(int from, int to){
    for (int i = 0; i < group.size(); i++){
        for (int j = 0; j < group.size(); j++){
            if (group[i][j] == from){
                group[i][j] = to;
            }
        }
    }
}

//사다리 찾기
void    findLadder(vector<vector<int>>& land, int& height, int& answer){
    int     minGap = 0;
    int     from = 0;
    int     to = 0;
    int     len = land.size();

	//최소값 찾기
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (i > 0 && group[i][j] != group[i - 1][j]){
                checkGap(land, minGap, from, to, i, j, i - 1, j);
            }
            if (i < len - 1 && group[i][j] != group[i + 1][j]) {
                checkGap(land, minGap, from, to, i, j, i + 1, j);
            }
            if (j > 0 && group[i][j] != group[i][j - 1]){
                checkGap(land, minGap, from, to, i, j, i, j - 1);
            }
            if (j < len - 1 && group[i][j] != group[i][j + 1]){
                checkGap(land, minGap, from, to, i, j, i, j + 1);
            }
        }
    }
	//연결한 구역 수정하기
    arrangeGroup(from, to);
	//사다리 설치 비용 저장
    answer += minGap;
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    
    group.assign(land.size(), vector<int>(land.size(), 0));
    makeGroup(land, height);
    while (count > 0) {
        findLadder(land, height, answer);
        count--;
    }
    return answer;
}

 

위의 코드로 실행한 결과, 시간초과가 발생한다.

 

우선, 서로 다른 구역의 높이 차이를 1번 확인하기 위해서 gap 변수를 선언하여 값을 저장했다.

또한, 최솟값을 구하는 부분도 gap을 sort 함수를 사용했다.

vector<pair<int, pair<int, int>>> gap;

void    makeGap(vector<vector<int>>& land){
    int len = land.size();
    pair<int, int>  tmp;
    
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (i < len - 1 && group[i][j] != group[i + 1][j]) {
                tmp = pair<int, int>(group[i][j], group[i + 1][j]);
                gap.push_back(pair<int, pair<int, int>>(abs(land[i][j] - land[i + 1][j]), tmp));
            }
            if (j < len - 1 && group[i][j] != group[i][j + 1]){
                tmp = pair<int, int>(group[i][j], group[i][j + 1]);
                gap.push_back(pair<int, pair<int, int>>(abs(land[i][j] - land[i][j + 1]), tmp));
            }
        }
    }
}

void    arrangeGroup(int from, int to){
    vector<pair<int, pair<int, int>>>::iterator it;
    
    it = gap.begin();
    while (it != gap.end()){
        if (it->second.first == from && it->second.second == to){
            it = gap.erase(it);
            continue;
        } else if (it->second.first == to && it->second.second == from){
            it = gap.erase(it);
            continue;
        } else if (it->second.first == to){
            it->second.first = from;
        } else if (it->second.second == to){
            it->second.second = from;
        }
        it++;
    }
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    int len = land.size();
    
    group.assign(len, vector<int>(len, 0));
    makeGroup(land, height);
    makeGap(land);
	sort(gap.begin(), gap.end());
    while (count > 1) {
		answer += gap.begin()->first;
		arrangeGroup(gap.begin()->second.first, gap.begin()->second.second);
        count--;
    }
    return answer;
}

이전 보다는 속도가 빨라졌지만, 여전히 시간초과가 발생했다.

 

고민을 하던 중...

 

gap 변수에서 값을 삭제하지 않고 문제를 해결하도록 arrangeGroup 함수를 수정했다.

findParent 함수를 만들어 두 구역이 연결되었는지 확인하고, 연결되지 않는 경우에 서로 연결하고 해당 비용을 더하도록 작성했다.

 

---

 

결과 코드

 

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

int cnt; //구역의 수
vector<vector<int>> group; //구역의 값
vector<pair<int, pair<int, int>>> gap; //인접한 서로 다른 구역

void    bfs(vector<vector<int>>& land, int& height, int x, int y, int num){
    int len = land.size();
    
    if (x > 0 && !group[x - 1][y]){
        if (abs(land[x][y] - land[x - 1][y]) <= height) {
            group[x - 1][y] = num;
            bfs(land, height, x - 1, y, num);
        }
    }
    if (y > 0 && !group[x][y - 1]){
        if (abs(land[x][y] - land[x][y - 1]) <= height) {
            group[x][y - 1] = num;
            bfs(land, height, x, y - 1, num);
        }
    }
    if (x < len - 1 && !group[x + 1][y]){
        if (abs(land[x][y] - land[x + 1][y]) <= height) {
            group[x + 1][y] = num;
            bfs(land, height, x + 1, y, num);            
        }
    }
    if (y < len - 1 && !group[x][y + 1]){
        if (abs(land[x][y] - land[x][y + 1]) <= height) {
            group[x][y + 1] = num;
            bfs(land, height, x, y + 1, num);            
        }
    }
}
//구역을 나누어 저장
void    makeGroup(vector<vector<int>>& land, int& height){
    int num = 1;
    int len = land.size();

    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (group[i][j] == 0) {
                group[i][j] = num;
                bfs(land, height, i, j, num);
                num++;
            }
        }
    }
    cnt = num - 1;
}
//서로 다른 구역이 인접한 경우 저장
void    makeGap(vector<vector<int>>& land){
    int len = land.size();
    pair<int, int>  tmp;
    
    for (int i = 0; i < len; i++){
        for (int j = 0; j < len; j++){
            if (i < len - 1 && group[i][j] != group[i + 1][j]) {
                tmp = pair<int, int>(group[i][j], group[i + 1][j]);
                gap.push_back(pair<int, pair<int, int>>(abs(land[i][j] - land[i + 1][j]), tmp));
            }
            if (j < len - 1 && group[i][j] != group[i][j + 1]){
                tmp = pair<int, int>(group[i][j], group[i][j + 1]);
                gap.push_back(pair<int, pair<int, int>>(abs(land[i][j] - land[i][j + 1]), tmp));
            }
        }
    }
}
//parent 변수 초기화
void    makeParent(vector<int>& parent, int size){
    parent.resize(size + 1);
    for (int i = 1; i <= size; i++){
        parent[i] = i;
    }
}
//연결된 구역 찾기
int     findParent(vector<int>& parent, int A){
    if (A == parent[A]) return A;
    return parent[A] = findParent(parent, parent[A]);
}
//크루스칼 알고리즘
int kruskal(){
    int         answer = 0;
    vector<int> parent;

    makeParent(parent, gap.size());
    for (int i = 0; i < gap.size(); i++){
        int x = findParent(parent, gap[i].second.first);
        int y = findParent(parent, gap[i].second.second);
        if (x != y){
            if (x > y){
                parent[x] = y;
            } else {
                parent[y] = x;
            }
            answer += gap[i].first;
        }
    }
    return answer;
}

int solution(vector<vector<int>> land, int height) {
    int len = land.size();
    
    group.assign(len, vector<int>(len, 0));
    makeGroup(land, height);
    makeGap(land);
    sort(gap.begin(), gap.end());
    return kruskal();
}