[Programmers] 석유 시추

프로그래머스

 

1. 구현 아이디어 1 - 시간 초과

1. BFS를 사용하여 '각 칸을 시작점으로 했을 때 얻을 수 있는 석유량'을 구한다.
2. 1번에서 구한 석유량을 더하여 '해당 열에서 얻을 수 있는 석유량'을 구한다.
3. 2번에서 구한 석유량끼리 비교하여 '얻을 수 있는 가장 많은 석유량'을 구한다.

 

#include <vector>
#include <queue>

using namespace std;

typedef vector<vector<bool>> vvb;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int solution(vector<vector<int>> land) {
    int answer = 0;
    
    // 1. 0번째 열부터 시작하여 한 칸씩 내려가면서 그 칸을 시작점으로 BFS를 진행
    for(int j=0; j<land[0].size(); j++) {
        vvb visited = vvb(land.size(), vector<bool>(land[0].size(), false));
        int col_total = 0; // 해당 열에서 얻을 수 있는 총 석유량
        
        for(int i=0; i<land.size(); i++) {
            // visited[i][j]거나 land[i][j]=0이면 continue
            if (visited[i][j] || land[i][j] == 0) continue;
            
            // BFS
            queue<pair<int, int>> q;
            q.push({i, j}); // {행, 열, cnt}
            int total = 0; // 해당 칸에서 얻을 수 있는 총 석유량
            
            while(!q.empty()) {
                int cx = q.front().first;
                int cy = q.front().second;
                q.pop();
                
                if (visited[cx][cy]) continue;
                visited[cx][cy] = true;
                total ++;
                
                for(int k=0; k<4; k++) {
                    int nx = cx + dx[k];
                    int ny = cy + dy[k];
                    
                    // Index out of range
                    if (nx < 0 || ny < 0 || nx >= land.size() || ny >= land[0].size()) continue;
                    // 빈 땅인 경우
                    if (land[nx][ny] == 0) continue;
                    // 이미 방문한 땅인 경우
                    if (visited[nx][ny]) continue;
                    
                    q.push({nx, ny});
                }
            }

            col_total += total;
        }
        
        if (answer < col_total) answer = col_total;
    }
    return answer;
}

 

visited 배열을 초기화하기 위해 최대 25만개짜리 배열을 500번 만들고 있어 해당 작업에만 1억 번이 넘는 연산이 필요하다.

 

2. 구현 아이디어 2 - 정답입니다

일반적인 BFS 문제인줄 알았는데, visited 배열을 사용하지 않고 문제를 풀 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였다.

 

 

구현 아이디어 1의 코드에서는 (2,0)에서 8칸을 추출했다는 것을 계산하고, (2,1)에서 8칸 추출을 다시 계산하게 된다.

 

이러한 반복을 줄이기 위해 set을 사용하여 해당 석유 덩어리의 열 좌표를 저장하고 각 열마다 석유량을 저장하는 벡터에 set의 값을 사용하여 석유량을 저장하면 된다.

 

#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef vector<vector<bool>> vvb;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int solution(vector<vector<int>> land) {
    int answer = 0;
    vector<int> total = vector<int>(land[0].size(), 0);
    
    // 1. 0번째 열부터 시작하여 한 칸씩 내려가면서 그 칸을 시작점으로 BFS를 진행
    for(int j=0; j<land[0].size(); j++) { // 열
        for(int i=0; i<land.size(); i++) { // 행
            // 이미 방문한 땅이거나 빈 땅일 경우
            if (land[i][j] == 0) continue;
            
            // BFS
            queue<pair<int, int>> q;
            set<int> s; // BFS 탐색 시 추출하는 가로 칸
            
            q.push({i, j}); // {행, 열, cnt}
            s.insert(j);
            land[i][j] = 0; // 방문한 칸은 0으로 만든다
            
            int cnt = 1;
            
            while(!q.empty()) {
                int cx = q.front().first;
                int cy = q.front().second;
                q.pop();
                
                for(int k=0; k<4; k++) {
                    int nx = cx + dx[k];
                    int ny = cy + dy[k];
                    
                    // Index out of range
                    if (nx < 0 || ny < 0 || nx >= land.size() || ny >= land[0].size()) continue;
                    // 빈 땅인 경우
                    if (land[nx][ny] == 0) continue;
                    
                    s.insert(ny);
                    land[nx][ny] = 0;
                    cnt++;
                    
                    q.push({nx, ny});
                }
            }

            for (auto elem : s) {
                total[elem] += cnt;
            }
        }
    }
    
    for (auto elem : total) {
        if (elem > answer) answer = elem;
    }
    
    return answer;
}