[프로그래머스 2레벨] 석유 시추 (C++)

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

using namespace std;

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

int N, M;

void bfs(int y, int x, int& cnt, set<int>& s, vector<vector<int>>& v)
{
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x] = true;
    cnt = 1;        
    s.insert(x);    

    while(!q.empty())
    {
        auto [yy, xx] = q.front();
        q.pop();

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

            if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if(visited[ny][nx] || !v[ny][nx]) continue;

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

int solution(vector<vector<int>> land) {
    int answer = 0;
    N = land.size(); //행의 개수
    M = land[0].size(); //열의 개수
    
    vector<int> ans(M, 0); 
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(!land[i][j] || visited[i][j]) continue;
            int cnt = 0; //석유 덩어리 카운트
            set<int>s; //열 번호 저장
            bfs(i, j, cnt, s, land);
            
            for(auto k : s)
            {
                ans[k] += cnt;
            }
        }
    }
    
    answer = *max_element(ans.begin(), ans.end());
    return answer;
}

 

기본적으로 석유 덩어리가 있는 경우 해당 위치를 기점으로 bfs 탐색을 하여 이어진 석유 덩어리 개수를 카운트한다.

 

여기서 열 별로 연결된 값을 체크해야한다.

열의 경우 한번만 체크하면 되니까 set을 통해서 해당 열 번호를 저장한다.

그리고 해당 열에 대해 따로 벡터를 선언하여 해당 열 번호 따른 카운트를 누적하여 저장한다.

이렇게 하면 해당 열에 대해서 누적하여 석유 덩어리 카운트가 계산되기 때문에, 이후 벡터의 최대 값만 반환해주면 된다.