[C++] 프로그래머스 [PCCP 기출문제] 2번 / 석유 시추

 

#include <string>
#include <vector>
#include <set>
#include <math.h>

using namespace std;

bool visited[500][500];

void dfs(int x, int y, int &count, set<int>& targetNum, const vector<vector<int>>& land)
{
    if (visited[x][y])
    {
        return;
    }

    visited[x][y] = true;
    count++;
    targetNum.insert(y);

    if (x + 1 < land.size())
    {
        if (land[x + 1][y] == 1)
        {
            dfs(x + 1, y, count, targetNum, land);
        }
    }
    if (y + 1 < land[x].size())
    {
        if (land[x][y + 1] == 1)
        {
            dfs(x, y + 1, count, targetNum, land);
        }
    }
    if (x - 1 >= 0)
    {
        if (land[x - 1][y] == 1)
        {
            dfs(x - 1, y, count, targetNum, land);
        }
    }
    if (y - 1 >= 0)
    {
        if (land[x][y - 1] == 1)
        {
            dfs(x, y - 1, count, targetNum, land);
        }
    }
    
}

int solution(vector<vector<int>> land)
{
    int answer = 0;
    vector<int> maxNum(land[0].size(), 0);

    for (int i = 0; i < land.size(); i++)
    {
        for (int j = 0; j < land[i].size(); j++)
        {
            if (land[i][j] == 1)
            {
                set<int> targetNum;
                int count = 0;

                dfs(i, j, count, targetNum, land);

                for (auto num : targetNum)
                {
                    maxNum[num] += count;
                }
            }
        }
    }

    for(int i = 0; i < maxNum.size(); i++)
    {
        answer = max(maxNum[i], answer);
    }

    return answer;
}

 

풀이

1. dfs로 석유 매립 지역과 석유량을 찾는다.

2. 매립 지역에 석유량을 추가해준다.

3. 최대로 가져올 수 있는 곳을 가져온다.

 

느낀점

레벨2 문제인데 한시간걸렸다. 코딩시간을 더 단축할 수 있도록 노력을 해야될 것 같다.

 

 

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

프로그래머스