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

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때 어떻게 풀지 고민했다. 처음에는 특정 사다리를 놓을 경우 최소값만 구하려고 했는데, 그렇게 풀면 최소값을 구하는 과정에서 A, B, C 지역이 전부 연결되어야하는데 B, C지역끼리만 연결되는 경우가 생기기 때문이였다.

 

그래서 BFS로 사다리가 없는 지역들을 구분하고, 구분된 지역에서 다른지역으로 갈 때 사다리를 최소로 놓도록 했다.

 

문제를 풀다보니 모든 지역을 잇기 위해 사다리를 놓는 비용의 합이 최소가 되어야 했기 때문에 이는 MST 문제와 같은 문제라는 것을 알았다.

 

그래서 가장 비용이 적게 드는 사다리를 놓은 다음에, 사다리를 놓아서 새롭게 갈 수 있는 지역이 생기면 그 지역에서 사다리를 놓을 수 있는 새 구역에 대한 비용을 priority queue에 삽입했다.

 

[아이디어 정리]

1. BFS로 사다리를 놓지 않아도 되는 지역을 구분한다. ex) 구역1, 구역2
2. 특정 구역의 x, y 좌표 값을 vector에 삽입한다. ex) vector[1] => 1번 구역에 대한 좌표들을 모아둠
3. 1번 구역부터 다른 구역에 놓을 수 있는 사다리의 비용들을 구하고 priority queue에 삽입다.
4. priority queue의 맨 앞에 있는 원소를 꺼내고 꺼낸 원소의 좌표가 방문한 적이 없는 지역이면 사다리를 놓는 지역을 결정한다.
5. 만약 방문한 적이 있다면, pop()하고 다음 원소를 탐색한다.
6. 위 과정을 구역 개수 만큼 반복한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
vector<vector<int>> realLand;
vector<vector<int>> landCost;
vector<int> landC;
vector<vector<pair<int,int>>> flu;
int ry,rx;
// 완전탐색 하되, 비용이 그 칸에 있는 비용보다 작으면 BFS시작, 크면 없애버리기 
void BFS(int h,int stY,int stX, int landNum)
{
    queue<pair<int,int>> Q;
    Q.push(make_pair(stY,stX));
    landCost[stY][stX]=landNum;
    int ny, nx, y,x,CT;
    while (!Q.empty())
    {
        y=Q.front().first;
        x=Q.front().second;
        Q.pop();
        for (int i=0; i<4; i++)
        {
            ny=y+dy[i];
            nx=x+dx[i];
            if (ny>=0&&ny<ry&& nx>=0&& nx<rx)
            {
                CT=abs(realLand[ny][nx]-realLand[y][x]);
                if (CT<=h && landCost[ny][nx]!=landNum)
                {
                    landCost[ny][nx]=landNum;
                    Q.push(make_pair(ny,nx));
                }
            }
        }
    }
    return;
}

struct cmp{
    bool operator()(pair<int,int> a, pair<int,int>b){
        return a.first > b.first;   
    }
};

vector<int> visited;
int landCalc(int landNum)
{
    int y,x,ny,nx,CT,minCT, minLandNum;
    vector<int>canV; //방문 가능한 노드 리스트
    canV.push_back(1);
    visited[1]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
    minLandNum=1;
    while(canV.size()<landNum)
    {
        minCT=10001;
        for (int i=0; i<flu[minLandNum].size(); i++)
        {
            y=flu[minLandNum][i].first;
            x=flu[minLandNum][i].second;
            for (int j=0; j<4; j++)
            {
                ny=y+dy[j];
                nx=x+dx[j];
                if (ny>=0&&ny<ry&& nx>=0&& nx<rx && visited[landCost[ny][nx]]==-1)
                {
                    CT=abs(realLand[ny][nx]-realLand[y][x]);
                    pq.push(make_pair(CT,landCost[ny][nx]));
                }
            }
        }
        while(true)
        {
            if(visited[pq.top().second]==-1)
            {
                minLandNum=pq.top().second;
                minCT=pq.top().first;
                visited[minLandNum]=minCT;
                pq.pop();
                break;
            }
            else
            {
                pq.pop();
            }
        }
        canV.push_back(minLandNum);
    }   
    int ans=0;
    for(int i=1; i<visited.size(); i++)
    {
        ans+=visited[i];
    }
    return ans;
}

int solution(vector<vector<int>> land, int height) {
    realLand=land;
    ry=land.size();
    rx=land[0].size();
    landCost=vector<vector<int>>(ry,vector<int>(rx,0));
    int lNum=0;
    for (int i=0; i<ry; i++)
    {
        for(int j=0; j<rx; j++)
        {
            if (landCost[i][j]==0)
            {
                lNum+=1;
                BFS(height,i,j,lNum);                
            }
        }
    }
    landC=vector<int>(lNum+1,10001);
    flu=vector<vector<pair<int,int>>>(lNum+1);
    visited=vector<int>(lNum+1,-1);
    for (int i=0; i<ry; i++)
    {
        for(int j=0; j<rx; j++)
        {
            flu[landCost[i][j]].push_back(make_pair(i,j));
        }
    }
    return landCalc(lNum);  
}

 

---

 

쉬운 문제 같았는데 생각보다 오래 걸렸다.

문제를 푸는 방법을 몇 번 수정했고, 처음에 priority queue를 사용하지 않았더니 시간 초과가 걸렸다.

다시 priority queue로 구현한다고 시간이 오래 걸린 문제였다... 분명 쉬워 보였는데;; 

 

프로그래머스