석유 시추[프로그래머스]

접근법:

각 석유덩어리의 크기를 계산한다.
이 석유 덩어리가 어떤 열을 선택할때 시추 할수 있는지 추가한다.

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

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

int solution(vector<vector<int>> land) {
    int answer = 0;
    int n = land.size();
    int m = land[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<int> sums(m, 0);
    
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(land[i][j] == 1 && !visited[i][j])
            {
                queue<vector<int>> q;
                q.push({i, j});
                visited[i][j] = true;
                int size = 0;
                set<int> cols;
                
                while(!q.empty())
                {
                    int x = q.front()[0];
                    int y = q.front()[1];
                    q.pop();

                    size++;
                    cols.insert(y);
                    
                    for (int d = 0; d < 4; ++d)
                    {
                        int nx = x + dx[d];
                        int ny = y + dy[d];

                        if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                        {
                            if (land[nx][ny] == 1 && !visited[nx][ny])
                            {
                                visited[nx][ny] = true;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
                
                for(auto col : cols)
                {
                    sums[col] += size;
                }
            }
        }
    }
    
    return *max_element(sums.begin(), sums.end());
}

접근법: (효율성 테스트 통과 실패)

각 열에서 석유를 만날때 까지 행을 증가시킨다.
석유를 만났다면, bfs를 통해 석유의 덩어리가 얼마나 큰지 구한다.
덩어리 밑에 또다른 덩어리가 있을수도있으니 재귀적으로 함수를 불러 아래 있는 덩어리를 구할 수 있도록 한다.

효율성 테스트 통과 실패 원인:

맵 전체를 뒤덮는 석유 덩어리가 있다면 매 열 마다 전체를 다시 계산하기 때문에 최악의 경우 제한 시간을 초과한다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

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

int bfs(int x, int y, int n, int m, const vector<vector<int>>& land, vector<vector<bool>>& visited)
{
    int cx = x;
    int cy = y;
    while(cx < n && (land[cx][cy] == 0 || visited[cx][cy]))
        cx++;

    if(cx >= n) return 0;
    //cout << "cx, cy : " << cx << ", " << cy << endl;
    
    queue<vector<int>> q;
    q.push({cx, cy});
    
    int size = 0;
    while(!q.empty())
    {
        int tx = q.front()[0];
        int ty = q.front()[1];
        q.pop();
        if(!visited[tx][ty])
        {
            size++;
            visited[tx][ty] = true;    
        } else continue;
        
        //cout << "{" << tx << ", " << ty << "}" << endl;
        for(int i = 0; i < 4; ++i)
        {
            int nx = tx + dx[i];
            int ny = ty + dy[i];
        
            if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            {
                if(land[nx][ny] == 1 && visited[nx][ny] == false)
                {
                    q.push({nx, ny});
                }
            }
        }
    }
    size += bfs(cx, cy, n, m, land, visited);
    //cout << size << endl;
    return size;
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    int n = land.size();
    int m = land[0].size();
    for(int i = 0 ; i < m; ++i)
    {
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        answer = max(answer, bfs(0, i, n, m, land, visited));
    }
    return answer;
}

###

이모티콘 할인 행사[프로그래머스]

과제 진행하기[프로그래머스]