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

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

프로그래머스

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

문제 유형 : bfs / dfs , 부분합, 다이나믹 프로그래밍

문제 난이도 : Level 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

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

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

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

 

풀이

아래 그림을 봐보자. 빨간 글씨는 각 인덱스별로 얻을 수 있는 최대의 개수를 말한다.

매 번 시추관을 놓는 위치별로 새로 탐색을 하면, 시간 초과 문제에 봉착하고 만다.

시간을 단축하는 비결은, 석유 덩어리 마다 단 한번씩만 순회한다는 것이다.

 

dp[i]테이블을 만든다. i번째에 시추관을 놓았을 때 최대 얻는 석유의 양을 저장한다.

각 덩어리의 탐색이 끝나면, 덩어리가 소속된 열들마다 석유 덩어리의 크기만큼 누적시키면 테이블에 저장이 된다.

모든 덩어리들을 탐색하고 나서, 테이블에 있는 가장 큰 값을 반환해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};
vector<int> table;


void bfs(pair<int, int> start, vector<vector<int>> &land, vector<vector<bool>> &visited) {
    const int n = land.size();
    const int m = land[0].size();
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = true;
    int cnt = 0;

    set<int> cols;

    while(!q.empty()) {
        auto curr = q.front();
        q.pop();
        int x = curr.first;
        int y = curr.second;

        cols.insert(y);
        cnt++;

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

            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(visited[nx][ny]) continue;
            if(!land[nx][ny]) continue;

            q.push({nx, ny});
            visited[nx][ny] = true;
        }
    }

    for(const auto &col : cols) {
        table[col] += cnt;
    }
}

int solution(vector<vector<int>> land) {
    const int n = land.size();
    const int m = land[0].size();
    table.resize(m);
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(land[i][j] && !visited[i][j]) {
                bfs({i, j}, land, visited);
            }
        }
    }

    return *max_element(table.begin(), table.end());
}