프로그래머스 250136 (PCCP 기출문제) 2번 / 석유 시추

1 개요

프로그래머스 250136 (PCCP 기출문제) 2번 / 석유 시추

• 프로그래머스 250136번 문제
• 프로그래머스 Lv. 2.1

2 C++

#include <string>
#include <vector>
#include <set>
using namespace std;

int dfs(vector<vector<int>>& land, int x, int y, int index, int n, int m) {
    if (x < 0 || x >= n || y < 0 || y >= m || land[x][y] != 1) {
        return 0;
    }
    land[x][y] = index;
    return 1 + dfs(land, x+1, y, index, n, m) + dfs(land, x-1, y, index, n, m) 
               + dfs(land, x, y+1, index, n, m) + dfs(land, x, y-1, index, n, m);
}


int solution(vector<vector<int>> land) {
    int n = land.size(), m = land[0].size();
    vector<int> oilClusterSizes;
    int clusterIndex = 2;

    // 모든 석유 덩어리에 대해 DFS 실행
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (land[i][j] == 1) {
                oilClusterSizes.push_back(dfs(land, i, j, clusterIndex, n, m));
                clusterIndex++;
            }
        }
    }

    // 각 열별로 석유량 계산
    int answer = 0;
    for (int j = 0; j < m; ++j) {
        set<int> oilInColumn;
        for (int i = 0; i < n; ++i) {
            if (land[i][j] > 1) {
                oilInColumn.insert(land[i][j]);
            }
        }
        int oil = 0;
        for (int o : oilInColumn) {
            oil += oilClusterSizes[o - 2];
        }
        answer = max(answer, oil);
    }
    return answer;
}