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

 

📌 제한 사항

• 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이면 석유가 있는 땅을 의미합니다.

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

void DFS(int x, int y, int &count, vector<int> &column, vector<vector<int>> &land){
    int n = land.size();
    int m = land[0].size();
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    land[x][y] = 0;
    count++;
    
    if(find(column.begin(), column.end(), y) == column.end()){
        column.push_back(y);
    }

    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < n && ny >= 0 && ny < m && land[nx][ny] == 1){
            DFS(nx, ny, count, column, land);
        }
    }
}

int solution(vector<vector<int>> land) {
    int n = land.size();
    int m = land[0].size();
    vector<int> columnOil(m, 0);
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(land[i][j] == 1){
                int count = 0;
                vector<int> column;
                
                DFS(i, j, count, column, land);
                
                for (int col : column) {
                    columnOil[col] += count;
                }
            }
        }
    }
    
    return *max_element(columnOil.begin(), columnOil.end());
}

---

📝 풀이

• land를 [0][0]부터 [n][m]까지 돌며 석유 덩어리를 찾습니다.
• land[i][j]가 1인 경우 DFS 탐색을 시작 하며 하나의 석유 덩어리를 찾습니다.
• DFS가 방문한 부분은 0으로 바꾸어 방문 여부를 기록합니다.
• DFS 함수에서 count를 참조로 받아 누적시켜 석유 덩어리 크기를 알 수 있습니다.
• 이 때 석유 덩어리를 포함하는 열의 정보들도 column에 저장합니다.
• 한 번의 DFS가 끝나면 열마다 시추하는 석유량을 columnOil에 누적합니다.
• 최종적으로 하나의 시추관에서 가장 많은 석유량은 columnOil의 최댓값이므로 이를 return 합니다.