[백준] 2232 : 지뢰

https://www.acmicpc.net/problem/2232

2232번: 지뢰

---

• 지뢰는 자신보다 높은 폭발 값에만 영향을 받기 때문에, 모든 지뢰가 터지기 위해서는 가장 큰 지뢰는 반드시 터져야 한다.
• 그런 식으로 가장 큰 지뢰가 터졌을 때 영향을 받는 모든 지뢰들을 처리해주고, 남은 지뢰들 중 가장 큰 지뢰를 다시 터트린다.
• 모든 지뢰가 터질 때 까지 큰 지뢰들부터 하나씩 터트려준다.
• 특정 구간에서 가장 큰 지뢰를 찾아 주변 지뢰들을 같이 터트리고, 남은 구간에 대해서 다시 반복하는 재귀 함수를 썼다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int mines[50001];
vector<int> answer;

int max_idx(int l, int r)           // 특정 구간에서 터트릴 지뢰 인덱스(최대값) 구하기
{
    int ret = l, val = mines[l];
    for(int i = l+1 ; i <= r ; i++)
    {
        if(mines[i] > val)
        {
            ret = i;
            val = mines[i];
        }
    }
    return ret;
}

void explode(int l, int r)          // 특정 구간 기준으로 재귀
{
    int point = max_idx(l, r);      // 해당 구간에서 터트릴 위치 가져와서
    answer.push_back(point);        // 출력벡터에 추가해주고
    int cur_l = point, cur_r = point;
    bool changed = true;
    while(changed)                  // 인덱스를 양쪽으로 퍼트려나가면서 지뢰 터짐 처리
    {
        changed = false;
        if(cur_l > l && mines[cur_l] > mines[cur_l - 1]) cur_l--, changed=true;
        if(cur_r < r && mines[cur_r] > mines[cur_r + 1]) cur_r++, changed=true;
    }
    if(cur_l > l) explode(l, cur_l-1);  // 양쪽 끝까지 지뢰 다 터트린 후 왼쪽 구간과 오른쪽 구간에 대해서 다시 재귀적으로 처리
    if(cur_r < r) explode(cur_r+1, r);
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i = 0 ; i < N ; i++) cin >> mines[i];
    explode(0, N-1);                                                            // 전체 구간에 대해서 재귀 호출 시작
    sort(answer.begin(), answer.end());
    for(int i = 0 ; i < answer.size() ; i++) cout << answer[i]+1 << '\n';       // 정렬 후 하나씩 출력
}