🖊️ 문제

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

---

🖊️ 생각

1. 석유 한 덩어리의 크기 찾기
   이거는 DFS를 통해서 연관된 애들의 크기를 찾음

2. 열 별로 시추 가능한 애들 구하기
   -> 석유 덩어리들을 구할 때, 각 열들에 대해 석유들의 크기를 미리 구해놓자 (dp)

흠..
이렇게 접근했다.

dfs할 때는 set에다가 석유에 해당하는 열들을 저장해놓고, dfs빠져나오면
dp[set에 해당하는 원소들]에 저장해놓고,
마지막에 쓱 훑으면서 최댓값만 구해게 해놨다.

근데,,
풀고 나서 다른 사람의 풀이를 보니까 bfs로 푸는거다 ! 허거덩

근데 알고봤더니, 내가 했던 풀이와 알고리즘 자체는 비슷했다.
다만, 나는 재귀를 너무 사랑해서^^ 모든걸 재귀로 풀었고, 이걸 queue로 풀면 bfs가 된다.

사실 재귀로 해서 인수 받고,, 하는거 넘 헷갈리고, 스택도 간당간당하다.
걍 이걸 queue로 풀면 된다.

---

🖊️ 풀이

#include <string>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

int n, m;

int arr[510][510];
bool visited[510][510] = {false,};

int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
int dp[501];

int GetOil(int x, int y, int cnt, set<int>& s) {
    bool flag = false;
    for (int i = 0 ; i < 4 ; i++) {
        int nextX = x + dir[0][i];
        int nextY = y + dir[1][i];
        
        if (arr[nextX][nextY] && !visited[nextX][nextY]) {
            flag = true;
            visited[nextX][nextY] = true;
            s.insert(nextY);
        	cnt = GetOil(nextX, nextY, cnt + 1, s);
        }
    }
    if (!flag) {
        return cnt;
    }
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    
    n = land.size();
    m = land[0].size();
    
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < m ; j++) {
            arr[i+1][j+1] = land[i][j];
        }
    }
    
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1; j <= m ; j++) {
            if (arr[i][j] && !visited[i][j]) {
                visited[i][j] = true;
                set<int> s;
                s.insert(j);
                int cnt = GetOil(i, j, 1, s);
                for (auto iter = s.begin() ; iter != s.end() ; iter++)
                    dp[*iter] += cnt;
            }
        }
    }
    
    for (int i = 1 ; i <= m ; i++) {
        answer = max(answer, dp[i]);
    }
    
    return answer;
}

---

🖊️ 고칠점

1. BFS라는걸 좀 생각하고 살기
2. 재귀가 밥먹여주지 않는다.
3. 편식금지