LV2 PCCP 기출문제 2번 석유 시추

[level2] [PCCP 기출문제] 2번 / 석유 시추

 

 

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

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

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

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

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

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

입출력 예

입출력 예 설명

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

제한시간 안내

정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

 

 

문제 풀이

다른 사람들의 풀이에서 힌트를 얻었습니다.

연결된 공간은 모두 같은 키 값을 가지고 있는 것이 좋습니다.

다른 사람들의 풀이와 다르게 map과 set을 적절히 사용하여 연산속도를 더했습니다.

 

연결된 석유는 단순히 BFS나 DFS를 사용하여 체크합니다.

방문한 공간은 방문했다는 표시를 남겨두고 연결된 공간과 같은 key를 가집니다.

같은 키값을 가진 공간이 확인되면 map<key, count>를 이용해 키값에 대응하는 값을 증가시켜줍니다.

 

송유관이 위에서 아래로 뚫으므로 같은 열에 있는 키값을 찾고 키값에 대응하는 값들을 더해줍니다.

더해준 값이 가지고 있는 최대값보다 크면 최대값을 변경해줍니다.

 

 

#include <string>
#include <vector>
#include <map>
#include <set>
#include <iostream>

using namespace std;

int LandKey[500][500];
bool LandCheck[500][500];
map<int, int> SumLand;

void DFS(vector<vector<int>>& land, int x, int y, int key)
{
    if (land[x][y] == 0) return;
    if (LandCheck[x][y]) return;

    // 왔다감
    LandCheck[x][y] = true;
    LandKey[x][y] = key;
    SumLand[key]++;

    // 상 하 좌 우
    if (y > 0)
        DFS(land, x, y - 1, key);
    if (y < land[x].size() - 1)
        DFS(land, x, y + 1, key);
    if (x > 0)
        DFS(land, x - 1, y, key);
    if (x < land.size() - 1)
        DFS(land, x + 1, y, key);
}


int solution(vector<vector<int>> land) {
    int answer = 0;

    vector<int> total(land[0].size());

    int key = 0;
    set<int> keys;

    for (int x = 0; x < land.size(); x++)
    {
        for (int y = 0; y < land[x].size(); y++)
        {
            if (land[x][y] == 0) continue;
            if (LandCheck[x][y]) continue;

            DFS(land, x, y, key);
            key++;
        }
    }

    // 위에서 아래로 쳌
    for (int y = 0; y < land[0].size(); y++)
    {
        int sum = 0;
        keys.clear();
        for (int x = 0; x < land.size(); x++)
        {
            if (!LandCheck[x][y]) continue;

            keys.insert(LandKey[x][y]);
        }

        for (int k : keys)
        {
            sum += SumLand[k];
        }

        if (answer < sum)
            answer = sum;
    }

    return answer;
}