[프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - C++

문제

🔗 프로그래머스 - [PCCP 기출문제] 2번 / 석유 시추

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 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

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

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

 

입출력 예

 

---

간단한? 그러나 정확성과 효율성을 모두 고려했을 때 생각해줘야 할 부분이 많아서 기록해놓는 문제.

처음 아이디어는 당연히 각 열별 BFS 탐색을 진행 후 최대 영역을 비교하면 시간초과가 날 것이 뻔하니,

 

1. 1회 BFS 탐색하여 인접한 석유 덩어리는 그룹별로 묶는다.

2. 덩어리 별 크기는 map을 통해 저장해준다.

3. 열별 탐색을 진행하면서 그룹을 set으로 세어 중복을 없앤 후 더한 크기를 비교한다.

 

였는데, 계속 효율성 부분에서 시간초과가 나더라(사실 정확도만 land 크기가 100이고 효율성은 500인걸 안봐서 segmentation fault가 더많이 뜸)

 

그래서 계속 해결책을 찾다가 배운 점들 정리하면 다음과 같다.

 

Lessons learned

- C++의 map과 set의 연산 속도는 log N → map<int, int>로 쓸거면 차라리 필요한 자료구조의 크기만큼 미리 정의해놓고(여기서는 각각 R * C + 1, group_id + 1) 접근하면 O(1)로 시간 단축 가능

- 읽기만 필요한 배열(vector)을 함수의 parameter로 넘겨줄거면, 차라리 값을 복사하는 방식(call-by-value) 보다는 '참조 기반' 전달(call-by-reference)로 수정

vector<vector<int> > land → const vector<vector<int>>& land

 

실제로 첫번째거만 수정하면 시간초과가 발생했는데,

참조 방식으로 바꿔주니까 바로 통과했다..ㅜㅜ

 

공부의 끝이없다..

 

코드

#include <string>
#include <vector>
#include <queue>
#define MAX 501

using namespace std;

bool visited[MAX][MAX] = { false };
int graph[MAX][MAX] = { 0 };
int dy[] = { 1, -1, 0, 0 };
int dx[] = { 0, 0, 1, -1 };

int BFS(int start_r, int start_c, int group_id, vector<vector<int> >& land) {
    queue<pair<int, int> > q;
    int r = land.size();
    int c = land[0].size();
    
    int group_cnt = 1;
    visited[start_r][start_c] = true;

    q.push(make_pair(start_r, start_c));

    while(!q.empty()) {
        int nr = q.front().first;
        int nc = q.front().second;
        graph[nr][nc] = group_id;
        
        q.pop();

        for(int i = 0; i < 4; i++) {
            if(nr + dy[i] < 0 || nr + dy[i] >= r || nc + dx[i] < 0 || nc + dx[i] >= c) continue;
            if(!visited[nr + dy[i]][nc + dx[i]] && land[nr + dy[i]][nc + dx[i]] == 1) {
                visited[nr + dy[i]][nc + dx[i]] = true;
                q.push(make_pair(nr + dy[i], nc + dx[i]));
                group_cnt++;
            }
        }
    }
    
    return group_cnt;
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    int r = land.size();
    int c = land[0].size();
    vector<int> group(r * c + 1, 0);
    
    int group_id = 0;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if(land[i][j] == 1 && !visited[i][j]) {
                group_id++;
                group[group_id] = BFS(i, j, group_id, land);
            }
        }
    }

    int max = 0;
    for(int j = 0; j < c; j++) {
        int count = 0;
        vector<bool> group_visited(group_id + 1, false);

        for(int i = 0; i < r; i++) {
            int gid = graph[i][j];
            if(gid != 0 && !group_visited[gid]) {
                count += group[gid];
                group_visited[gid] = true;
            }
        }

        max = max < count ? count : max;
    }

    return max;
}