프로그래머스 - PCCP 기출문제 2(250136)

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

프로그래머스

---

문제 설명

n x m 크기의 땅에 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있으며 가장 효율적인 시추를 위해 시추관을 수직으로 단 하나만 뚫을 때 가장 많은 석유를 뽑을 수 있는 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태이며 열과 열 사이 뚫을 수 없습니다.

프로그래머스 시추관 이미지

다음과 같은 땅에서는 8, 7, 2 크기의 석유 덩어리가 묻혀있으며 시추를 설치한 열은 석유 덩어리의 일부만 지나도 모든 석유를 뽑을 수 있습니다. 위와 같은 경우 7번 열에 설치하면 최대 9만큼의 석유를 얻을 수 있습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 주어질 때 시추관 하나로 가장 많이 뽑을 수 있는 석유량을 return하시오.

제한조건

1 <= n, m <= 500. land[i][j]는 0(땅) 또는 1(석유)입니다.

---

아이디어

1. land를 순회하며 석유가 있는지를 찾고, 만약 석유가 있다면 석유 덩어리를 체크합니다.
2. 체크한 석유덩어리가 어느 열까지 연결되어있는지 기록합니다.
3. 열까지 기록이 되었으면 해당 열에서 최대 석유량을 구합니다.

---

코드

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

using namespace std;

struct Oil{
    set<int> line;
    int size;
};

int maxRow, maxCol;
vector<int> oilCapacity;

void CheckOil(const vector<vector<int>> &land)
{
    vector<vector<int>> landCheck = vector(land.size(), vector<int>(land[0].size()));

    for(int r = 0; r < land.size(); r++)
    {
        for(int c = 0; c < land[0].size(); c++)
        {
            if(land[r][c] == 1 && landCheck[r][c] != 1)
            {
                vector<pair<int, int>> buf;
                buf.push_back({r, c});
                Oil oil;
                oil.size = 0;
                oil.line.insert(c);
                landCheck[r][c] = 1;
                while(!buf.empty())
                {
                    auto coord = buf.back();
                    buf.pop_back();
                    oil.size++;

                    if(!(coord.first-1 < 0) && (land[coord.first-1][coord.second] == 1) && (landCheck[coord.first-1][coord.second] != 1))
                    {
                        buf.push_back({coord.first-1, coord.second});
                        landCheck[coord.first-1][coord.second] = 1;
                    }       

                    if(!(coord.first+1 >= maxRow) && (land[coord.first+1][coord.second] == 1)  && (landCheck[coord.first+1][coord.second] != 1))
                    {
                        buf.push_back({coord.first+1, coord.second});
                        landCheck[coord.first+1][coord.second] = 1;
                    }

                    if(!(coord.second-1 < 0) && (land[coord.first][coord.second-1] == 1)  && (landCheck[coord.first][coord.second-1] != 1))
                    {
                        buf.push_back({coord.first, coord.second-1});
                        landCheck[coord.first][coord.second-1] = 1;
                        oil.line.insert(coord.second-1);
                    }
                    if(!(coord.second+1 >= maxCol) && (land[coord.first][coord.second+1] == 1)  && (landCheck[coord.first][coord.second+1] != 1))
                    {
                        buf.push_back({coord.first, coord.second+1});
                        landCheck[coord.first][coord.second+1] = 1;
                        oil.line.insert(coord.second+1);
                    }          
                }
                
                for(auto col : oil.line)
                {
                    oilCapacity[col] += oil.size;
                }
            }
        }
    }
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    vector<Oil> oil;
    maxRow = land.size(); maxCol = land[0].size();
    oilCapacity.resize(maxCol);
    CheckOil(land);
    return *max_element(oilCapacity.begin(), oilCapacity.end());
}

---

피드백

x,y에 +-1 위치이니 재귀로 dx = [0 , -1, 0, +1], dy = [-1, 0, +1, 0] 형식으로 바꾸는게 더 정석적인가? 생각이 듭니다.