[Programmers/C++] [PCCP 기출문제] 2번 / 석유 시추

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

 

💣 단순한 탐색으로는 효율성 테스트를 통과하지 못한다!

 

 시추관의 위치를 옮길 때마다 BFS 수행했던 첫 코드는 정확성 테스트는 통과하지만 효율성 테스트에서 처참히 실패하게 되는데..

 

결국 BFS를 한 번만 수행하는 게 요점인 것 같다. 수행하는 동안 최대한 많은 (석유)데이터를 뽑아먹을 궁리를 해야 한다!

 

 

우당탕탕 효율성 챙기기

 

문제

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

석유시추-1

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

석유시추-2

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

 

제한 사항

 

 

 

입출력 예시

입출력 예시

 

 

입출력 예시

 

 

 

---

 

풀이 

전체적인 석유 탐색은 BFS로 진행하였다.

한 번의 BFS에서 답을 얻어내기 위해서는 석유에 대한 데이터를 쏙쏙 뽑아놔야 한다.

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

struct Pos {
    Pos (int x, int y) {
        this->x = x;
        this->y = y;
    }
    int x;
    int y;
};

int solution(vector<vector<int>> land) {
    int dirX[4] = {1, -1, 0, 0};
    int dirY[4] = {0, 0, 1, -1};
    int n = land.size();    // 세로
    int m = land[0].size(); // 가로
    int answer = 0;
    int num = 1;            // 석유에 부여할 번호(tag)
    vector<vector<bool>> visited(n, vector<bool>(m, false));    // 방문 여부
    vector<vector<int>> oils(n, vector<int>(m, 0));             // 해당 석유가 속한 석유덩어리 번호
    map<int, int> oilBlocks;                                    // (석유덩어리 번호, 석유량)
    
    /* BFS */
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (visited[i][j] || land[i][j] != 1) continue;
            queue<Pos> q;
            q.push(Pos(i, j));
            visited[i][j] = true;   
            oils[i][j] = num;   // 해당 석유에 번호 부여
            
            int oil = 0;
            while (!q.empty()) {
                Pos curr = q.front();
                q.pop();
                oil++;
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = curr.x + dirX[dir];
                    int ny = curr.y + dirY[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (visited[nx][ny] || land[nx][ny] != 1) continue;
                    q.push(Pos(nx, ny));
                    visited[nx][ny] = true;
                    oils[nx][ny] = num; // 인접한 석유에도 번호 부여
                }
            }

            oilBlocks[num++] = oil; // 석유덩어리의 석유량 저장
        }
    }
    
    /* 석유 시추 */
    for (int j = 0; j < m; ++j) {
        int sum = 0; 
        set<int> s;     
        /* 시추관이 지나간 석유덩어리들을 set에 저장 */
        for (int i = 0; i < n; ++i) {
            s.insert(oils[i][j]);
        }
        /* set에 저장된 석유덩어리들의 석유량 계산 */
        for (int num : s) {
            sum += oilBlocks[num];
        }
        
        if (sum > answer) answer = sum;
    }

    return answer;
}

 

BFS동안, 석유가 있는 칸에 진입하면 인접한 석유들까지 한 덩어리로 판단하고, 모두 동일한 번호를 매겼다. -> oils

그리고 그 번호의 석유 덩어리의 석유량까지 측정해서 map컨테이너에 저장하였다. -> oilBlocks

• key -> 석유 덩어리의 번호 
• value -> 석유량

그림으로 보면 다음과 같다.

BFS동안 석유 덩어리별로 번호를 부여한다.

 

각 석유덩어리에 대한 석유량 정보는 map에 담게 된다.

위 oils를 이용해 각 석유 덩어리의 석유량을 측정한 값이다.

 

 

모든 석유에 대한 번호부여가 끝나면, 각 위치에서 석유 시추를 진행한다.

 

 

 

---