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

프로그래머스

N * M 크기의 격자 모양의 땅 속에서 석유가 발견되었습니다. 땅 아래로 시추관을 수직으로 하나만 뚫을 수 있을 때, 뽑을 수 있는 가장 많은 양의 시추는 얼마인지 구하시오

 

풀이방법

Union-Find, BFS 알고리즘을 이용하여 풀이해주었습니다.

우선 BFS를 이용하여 석유 덩어리의 크기를 구해줍니다. 이후 석유 덩어리에 해당되는 배열에 석유의 크기를 입력해줍니다.

그리고 석유 덩어리의 각 index들을 Union-Find를 이용하여 하나의 index를 바라보게 하였습니다.

 

vector<bool> visit(size, false);
for (int j = 0; j < land[0].size(); j++)
{
    int total = 0;
    for (int i = 0; i < land.size(); i++)
    {
        int idx = i * land[0].size() + j;
        int parent = Find(parents, idx);

        if (visit[parent] == false)
        {
            total += land[i][j];       
            visit[parent] = true;

        }
    }
    fill(visit.begin(), visit.end(), false);
    answer = max(answer, total);
}

이후 수직으로 덩어리들을 순회하며 가장 큰 값을 찾아주었습니다.

 

 

정답 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

void Union(vector<int>& parents, int a, int b);
int Find(vector<int>& parents, int a);

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int BFS(vector<vector<int>>& land, vector<vector<bool>>& visited, vector<int>& parents, int y, int x)
{
    vector<pair<int, int>> pos;
    queue<pair<int, int>> q;
    
    q.push({y, x});
    pos.push_back({y, x});
    
    int cnt = 1;
    while(!q.empty())
    {
        auto&[cy, cx] = q.front(); q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            
            if (ny < 0 || ny >= land.size() || nx < 0 || nx >= land[0].size() || 
                visited[ny][nx] || land[ny][nx] == 0)
                continue;
            
            visited[ny][nx] = true;
            q.push({ny, nx});
            pos.push_back({ny, nx});
            
            int cidx = cy * land[0].size() + cx;
            int nidx = ny * land[0].size() + nx;
            Union(parents, cidx, nidx);
            
            cnt++;
        }
    }
    
    for (auto& p : pos)
        land[p.first][p.second] = cnt;
    
    return cnt;
}

int solution(vector<vector<int>> land) {
    int answer = -11110;
    int size = land.size() * land[0].size();
    vector<vector<bool>> visited(land.size(), vector<bool>(land[0].size()));
    
    // parent 배열 초기화
    vector<int> parents(size);
    for (int i = 0; i < size; i++)
        parents[i] = i;
    
    // BFS를 이용하여 석유 덩어리 찾기
    for (int i = 0; i < land.size(); i++)
    {
        for (int j = 0; j < land[i].size(); j++)
        {
        	// 이미 체크한 곳이거나 석유가 있지않다면 continue
            if (visited[i][j] || land[i][j] == 0)
                continue;
            visited[i][j] = true;
            BFS(land, visited, parents, i, j);
        }
    }

    // 수직으로 시추관을 뚫어서 석유 덩어리 찾기
    vector<bool> visit(size, false);
    for (int j = 0; j < land[0].size(); j++)
    {
        int total = 0;
        for (int i = 0; i < land.size(); i++)
        {
            int idx = i * land[0].size() + j;
            int parent = Find(parents, idx);
            
            if (visit[parent] == false)
            {
                total += land[i][j];       
                visit[parent] = true;

            }
        }
        // 방문 배열 초기화
        fill(visit.begin(), visit.end(), false);
        answer = max(answer, total);
    }
    
    return answer;
}

void Union(vector<int>& parents, int a, int b)
{
    a = Find(parents, a);
    b = Find(parents, b);
    
    parents[b] = a;

}

int Find(vector<int>& parents, int a)
{
    if (parents[a] == a)
        return a;

    return parents[a] = Find(parents, parents[a]);
}