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

1 개요

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

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

2 C++

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

int N, M;
vector<vector<int>> Land;

int dfs(int x, int y, int index) {
    if (x < 0 || x >= N || y < 0 || y >= M || Land[x][y] != 1) {
        return 0;
    }
    Land[x][y] = index;
    return 1 + dfs(x+1, y, index) + dfs(x-1, y, index) + dfs(x, y+1, index) + dfs(x, y-1, index);
}


int solution(vector<vector<int>> land) {
    Land = land;
    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(i, j, clusterIndex));
                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;
}