[프로그래머스 C++] [PCCP 기출문제] 2번 / 석유 시추

 

[프로그래머스 C++] [PCCP 기출문제] 2번 / 석유 시추

 

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

프로그래머스

---

 

 

해결전략

 

너비우선탐색 BFS

맵 Map, 셋 Set

 

 

 

 

< 석유 매장량 구하기 >

• BFS를 돌려 석유 덩어리의 석유 매장량(= oilAmount)를 구한다.

 

< 석유 덩어리가 걸쳐있는 x 위치 다 담기 >

• BFS 시행 후 해당 석유 덩어리가 걸쳐있는 x를 모두 set<int> xLocation 에 담아준다.

 

< map 자료형에 x좌표에 대응되는 석유 매장량 추가하여 담기 >

•  set<int> xLocation 에 담긴 x 위치에 석유 매장량을 더해서 담는다.
• 매장된 석유 덩어리 끼리는 맡닿아 있지 않기 때문에 BFS 시행에 서로 영향을 주지 않는다.
  • 그렇기에 각각의 BFS 시행에서 단순히 더해도 된다. 
• answer를 max값을 갱신하여 x위치에서 구할 수 있는 최대 석유 매장량을 업데이트 한다.

---

 

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };
int r, c;
int answer = 0;
vector<vector<int>> ch;

// BFS 시행은 독립적이고 각각의 BFS로 얻은 석유 시추량은 서로 맡닿아 있지 않기 때문에 같은 X위치에 석유 매장량을 더해도 된다.
map<int, int> DrillLocation; // key: x 위치, value: 석유 매장량

void BFS(int startY, int startX, const vector<vector<int>>& land)
{
    int oilAmount = 1;
    set<int> xLocation; // x의 위치를 담는 set

    ch[startY][startX] = 1;
    queue<pair<int,int>> Q;
    Q.push({ startY, startX });
    xLocation.insert(startX);

    while (!Q.empty())
    {
        int currY = Q.front().first;
        int currX = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = currY + dirY[i];
            int nx = currX + dirX[i];

            if (ny < 0 || r <= ny || nx < 0 || c <= nx) continue;
            if (land[ny][nx] == 0) continue; // 석유가 없는 땅 continue;

            if (ch[ny][nx] == 0) {
                ch[ny][nx] = 1;
                Q.push({ ny, nx });
                oilAmount++; // 석유 매장량++
                xLocation.insert(nx);
                //cout << "  (ny, nx) = " << ny << ", " << nx << "\n";
            }
        }
    }

    for (const auto& iter : xLocation) {
        DrillLocation[iter] += oilAmount;
        answer = max(answer, DrillLocation[iter]);
        //cout << "iter = " << iter << ", DrillLocation[" << iter << "] = " << DrillLocation[iter] << "\n";
    }

    //cout << "oilAmount = " << oilAmount << "\n\n";
}

int solution(vector<vector<int>> land) {
    r = land.size();
    c = land[0].size();
    ch.resize(r, vector<int>(c));

    for (int y = 0; y < r; y++) {
        for (int x = 0; x < c; x++) {
            if (land[y][x] == 1 && ch[y][x] == 0) { // 석유가 있고 아직 방문하지 않은곳
                //cout << "(y, x) = " << y << ", " << x << "\n";
                BFS(y, x, land);
            }
        }
    }

    return answer;
}

int main() {
    vector<vector<int>> testcase1 = { {0, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 0, 1, 1, 0}, {1, 1, 1, 0, 0, 0, 0, 0},{1, 1, 1, 0, 0, 0, 1, 1 }};
    vector<vector<int>> testcase2 = { {1, 0, 1, 0, 1, 1}, {1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 0, 0}, {1, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1 }};
    cout << solution(testcase1) << "\n";
    cout << solution(testcase2) << "\n";
}

 

 

---