[Algorithm] Programmers :: 석유 시추

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

프로그래머스

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int oilMapIndex = 25001;
int oilSizes[60005] = { 0 };
 
struct Node
{
    int y;
    int x;
};
 
void UpdateOilMap(int startY, int startX, vector<vector<int>>& land)
{
    vector<Node> nodes = { {startY,startX} };
    queue<Node> q;
 
    int height = land.size();
    int width = land[0].size();
 
    q.push({ startY,startX });
    ++land[startY][startX];
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY < 0 || nextY == height) continue;
            if (nextX < 0 || nextX == width) continue;
            if (land[nextY][nextX] != 1) continue;
 
            ++land[nextY][nextX];
            nodes.push_back({ nextY, nextX });
            q.push({ nextY,nextX });
        }
    }
 
    int count = nodes.size();
    for (int i = 0; i < nodes.size(); ++i)
    {
        land[nodes[i].y][nodes[i].x] = oilMapIndex;
        oilSizes[oilMapIndex] = count;
    }
 
    ++oilMapIndex;
}
 
int solution(vector<vector<int>> land)
{
    int answer = 0;
 
    int height = land.size();
    int width = land[0].size();
 
    for (int i = 0; i < height; ++i)
    {
        for (int j = 0; j < width; ++j)
        {
            if (land[i][j] == 1)
            {
                UpdateOilMap(i, j, land);
            }
        }
    }
 
    for (int i = 0; i < width; ++i)
    {
        int count = 0;
        vector<bool> check(60005, false);
 
        for (int j = 0; j < height; ++j)
        {
            int index = land[j][i];
 
            if (check[index]) continue;
            else
            {
                check[index] = true;
                count += oilSizes[index];
            }
        }
 
        answer = max(answer, count);
    }
 
    return answer;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    //vector<vector<int>> land =
    //{
    //    {0, 0, 0, 1, 1, 1, 0, 0} ,
    //        {0, 0, 0, 0, 1, 1, 0, 0},
    //        {1, 1, 0, 0, 0, 1, 1, 0},
    //        {1, 1, 1, 0, 0, 0, 0, 0},
    //        {1, 1, 1, 0, 0, 0, 1, 1} 
    //};         //// 9
 
    /*vector<vector<int>> land =
    {
            {1, 0, 1, 0, 1, 1},
            {1, 0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0, 1},
            {1, 0, 0, 1, 0, 0},
            {1, 0, 0, 1, 0, 1},
            {1, 0, 0, 0, 0, 0},
            {1, 1, 1, 1, 1, 1}
    };*/        //// 16
 
 
    //vector<vector<int>> land =
    //{
    //    {1, 1, 1, 1},
    //    {1, 0, 0, 0},
    //    {1, 0, 1, 0},
    //    {1, 0, 0, 0},
    //    {1, 1, 1, 1},
    //};   //// 12
 
    cout << solution(land);
}
 
 
 

 

각 열에 시추관을 뚫었을 때 얻을 수 있는 기름칸의 최대개수를 구하는 문제이다.

 

나는 아래순서로 풀었다.

 

1.  UpdateOilMap 

     -> BFS를 이용해 덩어리크기를 구하고, land에 해당차례의 OilMapIndex로 덩어리들좌표에 전부 심어준다.

         UpdateOilMap을 마칠때마다 OilMapIndex를 ++해준다.

         즉 우리는 각 덩어리들을 인덱스로 관리한다.

 

2. 각 열마다 행을 순회한다. (시추관을 뚫는다)

    해당 칸이 0이 아닌 경우, 해당 칸의 index를 이전에 방문했는지 검사한다. (97번째 라인)

     검사 안한 index일 경우, 해당인덱스의 덩어리크기를 해당열의 count에 누적시킨다.

    모든 행을 순회했을 경우, answer에 최대값업데이트를 한다.

 

 

실수가 많이 날 수 있는 테스트케이스로는139번째 라인의 테스트케이스가 있으니 참고하길 바람.