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

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

프로그래머스

---

풀이

BFS로 배열 전체를 순회하며 석유가 있는 구간과 해당 구간에서 얻을 수 있는 석유 양을 추출했다.

이 때 석유가 있는 열의 범위를 구해 범위의 끝을 석유 양을 저장하여 표시해줬고, 가로 열을 순회하며 가장 양이 많은 열의 값을 반환했다.

 

코드를 조금씩 바꾸며 내 코드가 얼마나 비효율적인지를 깨달을 수 있었던 좋은 시간이었다..

생각을 더 해 본 후 코드를 짜는 습관을 들여야겠다.

---

답안 코드

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_LAND 510
typedef pair<int,int> pp;

bool visited[MAX_LAND][MAX_LAND];
int oils[MAX_LAND];
int N, M, miny, maxy;
queue <pp> Q;

// move to left, right, up, down
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int bfs(vector<vector<int>>& land, int x, int y) {
    int total = 0;

    Q.push({x, y});
    visited[x][y] = true;
    
    while (!Q.empty()) {
        x = Q.front().first, y = Q.front().second;
        Q.pop();
        
       // 해당 구역이 걸쳐있는 가로줄 구함
        miny = min(y, miny), maxy = max(y, maxy);
        
        // 석유 양 저장
        total++;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || N <= nx || ny < 0 || M <= ny || !land[nx][ny] || visited[nx][ny]) continue;

            visited[nx][ny] = true;
            Q.push({nx, ny});
        }
    }
    return total;
}

int solution(vector<vector<int>> land) {
    int answer = 0;

    N = land.size(), M = land[0].size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!land[i][j] || visited[i][j]) continue;
            
            miny = MAX_LAND, maxy = -1;
            
            // 해당 구역의 석유 양 추출 및 해당 구역의 가로 범위 저장
            int amount = bfs(land, i, j);       
            oils[miny] += amount, oils[maxy + 1] -= amount;
        }
    }
    
    int oilsInLine = 0;
    for (int i = 0; i < M; i++) {
        oilsInLine += oils[i];
        answer = max(answer, oilsInLine);
    }
    return answer;
}

 

 

 

+ DFS 탐색도 가능!

#include <vector>
#include <algorithm>

using namespace std;

#define MAX_LAND 510
typedef pair<int,int> pp;

bool visited[MAX_LAND][MAX_LAND];
int oils[MAX_LAND];
int N, M, miny, maxy;

// move to left, right, up, down
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int dfs(vector<vector<int>>&land, int x, int y) {
    int totalOilInField = 1;
    
     // 해당 지점 방문 표시
    visited[x][y] = true;

    // 해당 구역이 걸쳐있는 가로줄 구함
    miny = min(y, miny), maxy = max(y, maxy);
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || N <= nx || ny < 0 || M <= ny || !land[nx][ny] || visited[nx][ny]) continue;
        
        // 현재 구역의 석유 양 계산 
        totalOilInField += dfs(land, nx, ny);
    }

    return totalOilInField;
}

int solution(vector<vector<int>> land) {
    int answer = 0;

    N = land.size(), M = land[0].size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!land[i][j] || visited[i][j]) continue;
            
            miny = MAX_LAND, maxy = -1;
            
            // 해당 구역의 석유 양 추출 및 해당 구역의 가로 범위 저장
            int amount = dfs(land, i, j);       
            oils[miny] += amount, oils[maxy + 1] -= amount;
        }
    }
    
    int oilsInLine = 0;
    for (int i = 0; i < M; i++) {
        oilsInLine += oils[i];
        answer = max(answer, oilsInLine);
    }
        
    return answer;
}

---

코드 1 - 메모리 부족

- 석유가 있는 각 구역마다 번호를 매겨 이를 각 열마다 스택에 저장해뒀고, 순회하며 각 열에 저장된 구역 번호의 양을 더해주며 계산했다. 

 

정확성 테스트 마지막에서 (signal: aborted (core dumped)) 실패, 모든 효율성 테스트케이스에서 탈락

위의 오류가 저장공간 부족이라는 의미인 것 같아 스택을 쓰면 안 된다고 판단, 다른 방법을 찾아봤다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX_LAND 500

using namespace std;

bool visited[MAX_LAND][MAX_LAND];
stack <int> oilsInLine[MAX_LAND];
int N, M, fieldNum;

// move to left, right, up, down
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int dfs(vector<vector<int>> land, int x, int y) {
    int totalOilInField = 1;
    
    // 해당 지점 방문 표시
    visited[x][y] = true;
    
    // 가로줄에 해당 구역의 정보가 없다면 추가
    if (oilsInLine[y].empty() || (oilsInLine[y].size() && oilsInLine[y].top() != fieldNum)) {
        oilsInLine[y].push(fieldNum);
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || N <= nx || ny < 0 || M <= ny || !land[nx][ny] || visited[nx][ny]) continue;
        
        // 현재 구역의 석유 양 계산 
        totalOilInField += dfs(land, nx, ny);
    }
    
    // 현재까지 구한 석유 양 반환
    return totalOilInField;
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    vector <int> oilsInField(MAX_LAND);

    N = land.size(), M = land[0].size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!land[i][j] || visited[i][j]) continue;
            
            // 석유가 있는 구역이라면 해당 구역의 석유 양 추출(by dfs) 및 저장
            oilsInField[fieldNum] = dfs(land, i, j);
            fieldNum++;
        }
    }
    
    // 가로 줄을 순회
    for (int i = 0; i < M; i++) {
        int amount = 0;
        
        // 해당 가로줄에서 얻을 수 있는 총 석유의 양 계산 후 최대 값 찾기
        while (!oilsInLine[i].empty()) {
            amount += oilsInField[oilsInLine[i].top()];
            oilsInLine[i].pop();
        }
        answer = max(amount, answer);
    }
    return answer;
}

 

---

코드 2 - 시간 초과

- 코드 1과 원리는 동일하나 각 구역의 석유 양을 구할 때 y축 범위의 min ~ max를 구했고,

구역 1개를 구할 때마다 min_y ~max_y 범위에 석유의 양을 더해주었다.

 

정확성 테스트 통과, 효율성 테스트 2, 3 시간초과

 

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

#define MAX_LAND 500

using namespace std;

bool visited[MAX_LAND][MAX_LAND];
int oilsInLine[MAX_LAND];
int N, M;
int miny, maxy;

// move to left, right, up, down
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int dfs(vector<vector<int>> land, int x, int y) {
    int totalOilInField = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || N <= nx || ny < 0 || M <= ny || !land[nx][ny] || visited[nx][ny]) continue;
        
         // 해당 지점 방문 표시
        visited[nx][ny] = true;

        // 해당 구역이 걸쳐있는 가로줄 구함
        miny = min(ny, miny), maxy = max(ny, maxy);
        
        // 현재 구역의 석유 양 계산 
        totalOilInField += dfs(land, nx, ny);
    }

    return totalOilInField;
}

int solution(vector<vector<int>> land) {
    int answer = 0;

    N = land.size(), M = land[0].size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!land[i][j] || visited[i][j]) continue;
            
            miny = MAX_LAND, maxy = -1;
            
            // 해당 구역의 석유 양 추출 및 해당 라인에 석유 양 저장
            int amount = dfs(land, i, j);        
            for (int k = miny; k <= maxy; k++)
                oilsInLine[k] += amount;
        }
    }
    
    // 가로 줄을 순회하며 가장 많은 양을 시추할 수 있는 열 구함
    for (int i = 0; i < M; i++)
        answer = max(answer, oilsInLine[i]);
    return answer;
}

 

---

코드 3 - 효율성 테스트 실패

- 탐색 방법을 DFS -> BFS로 바꿨다.

- 석유 구역의 범위에 값을 모두 저장하는 것이 아닌, 양 끝에만 표시하여 반복문을 한 번만 돌아 답을 구하는 방식 (누적합)으로 바꿨다.

 

효율성 테스트 2, 3번 실패

시간 초과면 초과지 실패는 도대체 뭘까...
-------> 구역의 끝을 표시할 때 max_y 값을 구해 max_y + 1 인덱스에 값을 저장했는데, 배열의 크기가 주어진 MAX 값까지라 실패였다. MAX_LAND의 크기를 키워주니 시간초과 오류로 바뀜

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_LAND 500
typedef pair<int,int> pp;


bool visited[MAX_LAND][MAX_LAND];
int oils[MAX_LAND];
int N, M;
int miny, maxy;
queue <pp> Q;

// move to left, right, up, down
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int bfs(vector<vector<int>> land, int x, int y) {
    int total = 0;

    Q.push({x, y});
    visited[x][y] = true;
    
    while (!Q.empty()) {
        x = Q.front().first, y = Q.front().second;
        Q.pop();
        
        total++;
        
       // 해당 구역이 걸쳐있는 가로줄 구함
        miny = min(y, miny), maxy = max(y, maxy);
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || N <= nx || ny < 0 || M <= ny || !land[nx][ny] || visited[nx][ny]) continue;

            // 해당 지점 방문 표시
            visited[nx][ny] = true;
            Q.push({nx, ny});
        }
    }
    return total;
}

int solution(vector<vector<int>> land) {
    int answer = 0;

    N = land.size(), M = land[0].size();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!land[i][j] || visited[i][j]) continue;
            
            miny = MAX_LAND, maxy = -1;
            
            // 해당 구역의 석유 양 추출 및 해당 구역의 가로 범위 저장
            int amount = bfs(land, i, j);       
            oils[miny] += amount, oils[maxy + 1] -= amount;
        }
    }
    
    int oilsInLine = 0;
    for (int i = 0; i < M; i++) {
        oilsInLine += oils[i];
        answer = max(answer, oilsInLine);
    }
        
    return answer;
}

 

---

코드 4 - 답안 코드 (제일 위의 코드와 동일)

코드 3에서 주어진 land 벡터를 함수에 불러올 때 참조자로 불러오니 통과했다. (해당 부분만 변경)

앞으로도 참조자를 쓰는 습관을 들여야겠다..