[프로그래머스 lv 2] [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

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

입출력 예landresult

[[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

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

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

시추관의 위치획득한 덩어리총 석유량

1	[12]	12
2	[12]	12
3	[3, 12]	15
4	[2, 12]	14
5	[2, 12]	14
6	[2, 1, 1, 12]	16

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

---

제한시간 안내

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

---

풀이

기본적인 완전탐색 방법은

1. 어떤 열을 파다가 석유가 있다면,
2. DFS를 활용해 해당 칸에 연결된 모든 석유 칸들의 수를 세고,
3. 바닥까지 파내려가며 그 석유 칸의 수를 더해서 한 열을 팠을 때 얻은 석유의 수를 구하고,
4. 모든 열에 대해 똑같은 작업을 진행해 어떤 열이 가장 많은 석유를 얻었는가를 비교한다.

정도로 떠올릴 수 있다.

그러나 이 문제는 완전탐색을 하면 효율성 테스트 시 시간초과가 발생한다. 따라서 약간의 최적화가 필요하다.

 

내가 생각한 아이디어는 아래와 같다.

1. 어떤 열을 파내려가다가 석유(1)를 마주치면,
2. 해당 웅덩이에 석유가 몇 칸 들어있는지 DFS를 활용해 계산한다. (SuckOil)
3. 해당 웅덩이에 번호(2~)를 붙이고 알아낸 석유량을 기록한다. (poolMap)
4. 지도(land)에 웅덩이에 해당하는 모든 칸들은 석유 표시(1) 대신 해당 웅덩이의 번호(2~)를 표시한다.
5. 마주친 웅덩이들의 번호를 기록한다.(encounteredPool)
6. 열의 끝까지 파내려왔으면 기록한 웅덩이들의 번호를 보고 마주친 석유 량을 계산한다.

여기서 웅덩이 번호는 2부터 시작해서 점차 증가한다.

 

이렇게 웅덩이 번호와 석유량을 기록하고, 지도에 이미 발견한 석유들은 웅덩이 번호로 표시하여,

이미 발견한 석유 웅덩이의 석유량을 다시 계산하지 않도록 한 것이다.

 

코드

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

using namespace std;
int rowCount;
int colCount;
map<int, int> poolMap;
int poolIdx = 2;
void SuckOil(vector<vector<int>>& land, int r, int c, int& count)
{
    if(land[r][c] != 1)
        return ;

    land[r][c] = poolIdx;
    count ++;

    if(r-1 >= 0)
        SuckOil(land, r-1, c, count);
    if(r+1 < rowCount)
        SuckOil(land, r+1, c, count);
    if(c-1 >= 0)
        SuckOil(land, r, c-1, count);
    if(c+1 < colCount)
        SuckOil(land, r, c+1, count);
}
int solution(vector<vector<int>> land) {
    rowCount = land.size();
    colCount = land[0].size();
    int maxOilCount = 0;
    
    for(int c = 0; c < colCount; c++)
    {
        set<int> encounteredPool;
        for(int r = 0; r < rowCount; r++)
        {
            if(land[r][c] == 1)
            {
                int poolOilCount = 0;
                SuckOil(land, r,c,poolOilCount); 
                poolMap[poolIdx] = poolOilCount;
                encounteredPool.insert(poolIdx);
                poolIdx++;
            }
            else if( land[r][c] > 1)
            {
                encounteredPool.insert(land[r][c]);
            }
            
        }
        int encounteredOilCount = 0;
        for(auto iter = encounteredPool.begin(); iter != encounteredPool.end(); iter++)
        {        
            encounteredOilCount += poolMap[*iter];
        }

        maxOilCount = max(maxOilCount, encounteredOilCount);
    }
    return maxOilCount;
}