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

문제 설명

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

 

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

 

 

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

 

 

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

시추관의 위치	획득한 덩어리	총 석유량
1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7, 2]	9
8	[2]	2

     

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

 

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

 

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
• 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
• land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
• land[i][j]는 0 또는 1입니다.
• land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
• 정확성 테스트 케이스 제한사항
• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
• 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
  • 효율성 테스트 케이스 제한사항
    • 주어진 조건 외 추가 제한사항 없습니다.

 

입출력 예

land	result
[[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]]	9
[[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]]	16

---

문제 해설

 

전체탐색이나, 효율성이 들어가있음으로, 문제 자체는 DFS또는 BFS로 그대로 작성해서 풀면 안된다는 의미이다.

데이터의 전체 정렬 이후 그 정렬된 데이터를 활용해서 문항을 풀어야 효율성 테스트에서 성공한다.

---

첫 번째 시도

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

using namespace std;
void DFS(vector<vector<int>>& land, vector<vector<int>>& visit, int h, int w, int& answer)
{
    if(land[h][w] == 0 || visit[h][w] == 1) return;
    visit[h][w] = 1;
    answer++;
    if(h+1 < land.size() && visit[h+1][w] == 0 && land[h+1][w] == 1)
        DFS(land, visit, h+1, w , answer);
    if(h-1 >= 0 && visit[h-1][w] == 0 && land[h-1][w] == 1)
        DFS(land, visit, h-1, w , answer);
    if(w+1 < land[0].size() && visit[h][w+1] == 0 && land[h][w+1] == 1)
        DFS(land, visit, h, w+1 , answer);
    if(w-1 >= 0 && visit[h][w-1] == 0 && land[h][w-1] == 1)
        DFS(land, visit, h, w-1 , answer);
}

int solution(vector<vector<int>> land) {
    set<int> answer_set;
    for(int i = 0; i < land[0].size(); i++) {
        int answer = 0;
        vector<vector<int>> visit(land.size(), vector<int>(land[0].size(), 0));
        for(int j = 0; j < land.size(); j++)
            DFS(land, visit, j, i, answer);
        answer_set.insert(answer);
    }
    for(auto& def : answer_set)
        cout << def << endl;
    return *answer_set.rbegin();
}

실패

 

귀찮아서 그냥 문제 전체에 DFS로 순환참조를 진행했는데, 모든 객체가 스스로 탐색할 때 DFS를 각각 진행하게 됨으로 매우 비효율적인 코드가 되었다.

---

두 번째 시도

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

using namespace std;

map<int, int> soil;

bool FMax(const std::pair<int, int>& p1, const std::pair<int, int>& p2) {
    return p1.second < p2.second;
}

void DFS(vector<vector<int>>& land, int h, int w, int& answer, set<int>& chack)
{
    if (land[h][w] == 0) return;
    land[h][w] = 0;
    chack.insert(w);
    answer++;
    if (h + 1 < land.size() && land[h + 1][w] == 1)
        DFS(land, h + 1, w, answer, chack);
    if (h - 1 >= 0 && land[h - 1][w] == 1)
        DFS(land, h - 1, w, answer, chack);
    if (w + 1 < land[0].size() && land[h][w + 1] == 1)
        DFS(land, h, w + 1, answer, chack);
    if (w - 1 >= 0 && land[h][w - 1] == 1)
        DFS(land, h, w - 1, answer, chack);
}

int solution(vector<vector<int>> land) {
    set<int> answer_set;
    for (int i = 0; i < land[0].size(); i++) {
        for (int j = 0; j < land.size(); j++) {
            int answer = 0;
            set<int> chack;
            DFS(land, j, i, answer, chack);
            for (auto& def : chack)
                soil[def] += answer;
        }
    }
    return max_element(soil.begin(), soil.end(), FMax)->second;
}

성공

 

그냥 전체 순회를 처음에 전부 진행해버리고, 왼쪽부터 진행하게 됨으로, 석유는 좌측끝부터 우측끝까지의 w좌표를 기입할 수 있게된다.

 

그래서, 석유를 발견했을 때, 해당 석유의 시작점을 기입하고, DFS를 진행할 때, set으로 정렬된 w좌표를 넣어서 중복값을 날려준다.

 

그러면, 해당 석유 웅덩이에 접근할 수 있는 w좌표값을 가진 set이 나오는데, 이 set을 map의 지정된 key에 중첩연산 해준다음,

 

가장 큰 map의 값을 return하면 더 빠르게 사용이 가능하다.