프로그래머스 문제 - 석유 시추

프로그래머스 석유 시추 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에 석유가 있습니다.
여러 덩이로 나누어 묻혀있으며, 시추관을 수직으로 단 하나만 뜷을 수 있을 때 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾아야합니다.
만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있으며, 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다.

문제 풀이

1 <= n, m <= 500크기의 땅이 주어집니다.
문제가 정확성과 효율성을 체크하기 때문에 최소한으로 계산하여 답을 찾아내야 합니다.

일단 여러 덩이로 되어 있는 석유의 양을 체크해주는 것이 나중에 계산할 때 편해지므로, 재귀를 통해 각 덩이에 얼마의 석유가 존재하는지 확인해줍니다.
이후 수직으로 관을 뜷어주면서 석유가 있을 때마다 그 석유 덩이의 양을 더해주면서 총 합을 계산해준 후, 여러 위치 중 가장 많은 석유를 뽑아낸 양을 찾아주면 됩니다.

하지만 만약 'ㄷ' 'ㅂ' 'ㅁ'모양으로 커다랗게 석유가 매장되어 있을 경우 같은 석유를 여러 번 더해버리는 상황이 발생할 수 있습니다.
이를 해결하기 위해 석유의 양을 체크하면서 수직으로 시추관을 꽃았을 때 현재 덩이의 석유를 뽑을 수 있는 위치를 미리 알아내어 배열에 저장해준 후, 석유의 양을 계산하고 뽑아낼 수 있는 위치의 배열에 값을 더해줍니다. 이런식으로 모든 덩이를 찾아 계산하면 손쉽게 답을 찾아낼 수 있습니다.

예를 들어
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
처럼 땅이 있다면 추가로 가로 크기만큼 배열을 하나 만들어줍니다.
오른쪽 위의 덩이를 확인해보면 시추관으로 뜷었을 때 석유를 뽑아낼 수 있는 위치는 4, 5, 6, 7번째 위치이므로 만들어진 배열의 4, 5, 6, 7위치에 석유의 양만큼 더해줍니다.
그렇게 되면 만들어진 배열은
0 0 0 7 7 7 7 0 0
으로 됩니다.

위와 같은 방법으로 모든 덩이를 확인해주면
8 8 8 7 7 7 9 2
배열이 완성되고 이 중 제일 큰 수를 찾아주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> landMap;
vector<int> checkGetOil;
int oilCount;

void CheckOilCount(int x, int y)
{
    int dirX[4] = {0, 0, 1, -1};
    int dirY[4] = {1, -1, 0, 0};
    
    //시추관을 꽂으면 석유를 뽑을 수 있는 위치 저장
    checkGetOil[y] = 1;
    
    oilCount++;
    
    landMap[x][y] = 0;
    for(int i = 0; i < 4; i++)
    {
        if(x + dirX[i] < 0 || x + dirX[i] >= landMap.size() || y + dirY[i] < 0 || y + dirY[i] >= landMap[0].size())
            continue;
        
        if(landMap[x + dirX[i]][y + dirY[i]] == 1)
        {
            CheckOilCount(x + dirX[i], y + dirY[i]);
        }
    }
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    vector<int> totalHeightOil(land[0].size(), 0);
    
    landMap = land;
    oilCount = 0;
    
    checkGetOil.assign(land[0].size(), 0);
    
    for(int i = 0; i < landMap.size(); i++)
    {
        for(int j = 0; j < landMap[i].size(); j++)
        {
            if(landMap[i][j] == 1)
            {
                oilCount = 0;
                CheckOilCount(i, j);
                for(int k = 0; k < checkGetOil.size(); k++)
                {
                    if(checkGetOil[k] == 1)
                    {
                        totalHeightOil[k] += oilCount;
                    }
                }
                checkGetOil.assign(land[0].size(), 0);
            }
        }
    }
    
    for(int n : totalHeightOil)
    {
        answer = answer < n ? n : answer;
    }
    
    return answer;
}

출저

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