[백준 BOJ] 2232번 지뢰 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 그리디 알고리즘 활용 문제

백준의 2232번 문제는 그리디 알고리즘 방식으로 해결을 시도해야 하는 문제이다.

해당 문제는, 각 지뢰의 충격 강도가 입력으로 주어질 때 모든 지뢰를 터뜨리기 위해 직접 처리해야 하는 지뢰의 최소 개수를 구하여 출력해야 하는 문제이다.

이때 지뢰는 인접한 곳에서 자신의 충격 강도를 초과하여 힘을 받으면 터지는 원리임을 고려하면서 문제 해결을 시도하면 된다.

 

문제에도 충분히 설명되어 있는 부분이긴 하나, 예제 1번에 대한 설명을 여기에 자세히 풀어서 적어보고자 한다.

1) 1 2 5 4 3 3 6 6 2
7번의 지뢰(6)를 터뜨린다면, 왼편에 있는 지뢰는 터지겠으나 오른편에 있는 지뢰는 터지지 않는다.

2) 1 2 5 4 3 3 6 6 2
8번의 지뢰(6)를 터뜨린다면, 왼편에 있는 지뢰는 이미 터졌으나 오른편에 있는 지뢰는 터지게 된다.

3) 1 2 5 4 3 3 6 6 2
3번의 지뢰(5)를 터뜨린다면, 아래처럼 연쇄 반응이 발생하게 된다.
- 인접한 왼편의 지뢰가 터지면서, 그 왼편의 지뢰로도 2의 충격이 가하여 왼편 끝까지 터지게 된다.
- 인접한 오른편의 지뢰가 터지면서, 그 오른편의 지뢰로도 4의 충격이 가하여 오른편 끝까지 터지게 된다.

=> 이로써 3번, 7번, 8번의 지뢰를 직접 터뜨린다면 모든 지뢰가 연쇄 반응을 일으키며 모두 터뜨릴 수 있다고 볼 수 있다.

 

필자는 매우 그리디하게 지뢰의 충격 강도가 가장 센 것 위주로 터뜨리면서 인접한 지뢰를 하나씩 터뜨리는 방식으로 연산을 진행하였다.

이미 터진 지뢰이거나 존재하지 않는 지뢰의 경우에는 -1로 표기하면서, 모든 지뢰 유무를 체크해주기도 하였다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 지뢰의 개수(n)를 입력받는다.

 

2) 지뢰의 충격 강도를 각각 저장할 벡터 bomb를 미리 선언해 둔다.

그리고 충격 강도 기준으로 내림차순 정렬을 할 벡터 bomb_sort에 대해서도 미리 선언해 두었다.

(이때 first에는 지뢰의 위치를, second에는 지뢰의 충격 강도로 하여 한 쌍의 데이터를 이루며 저장하고자 한다.)

 

3) 입력을 받기 이전에, bomb에 -1 값을 삽입하여 지뢰가 없는 끝부분을 표시해 두도록 하였다.

 

4) 1부터 n까지 하여, 반복문을 통해 i값을 순회하며 아래의 연산을 취한다.

- 각 지뢰의 충격 강도(num)를 입력받도록 한다.

- bomb에 num의 값을 즉시 삽입한다.

- bomb_sort에는 {i, num} 쌍으로 하여 값을 삽입한다. (i번째에 num의 충격 강도를 가진 지뢰가 있음을 뜻한다.)

 

5) 3)과 마찬가지로, bomb에 -1 값을 삽입하여 지뢰가 없는 끝부분을 표시해 두도록 하였다. 

 

6) bomb_sort에 대하여, sort() 함수를 통해 정렬을 수행한다.

이때, compare 함수를 별도로 구성하여 충격 강도가 저장된 second값에 대하여 내림차순 정렬되게끔 하였다.

 

7) 직접 터뜨릴 지뢰의 위치를 저장할 벡터 result를 미리 선언해 둔다.

 

8) n의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

(해당 반복문으로 bomb_sort의 요소값에 하나씩 접근하는데, 6)의 정렬로 인하여 충격 강도가 높은 지뢰의 값을 우선적으로 탐색한다.)

- 현재 탐색하고 있는 요소에 대하여 지뢰의 위치를 loca에, 지뢰의 충격 강도를 p에 저장하도록 한다.

- result에 loca의 값을 저장하고 현재 위치의 bomb 값을 -1로 변경하여, 해당 지뢰를 직접 터뜨리도록 한다.

- power 변수에 p값을 저장한 뒤, 왼편 또는 오른편에 있는 지뢰의 각 값에 대해 접근한다. 

(연쇄 반응이 발생할 수 있을 때, power의 값을 갱신하고 이 power의 값으로 인접한 지뢰에 연이어 충격을 가하게끔 하였다.)

• 접근하고자 하는 지뢰의 bomb값이 -1이라면 이미 터진 지뢰이거나 지뢰가 존재하지 않음을 뜻한다. 그리고 power 값이 현재 접근하고 있는 bomb의 값보다 작거나 같은 경우에는 연쇄 반응으로 터뜨릴 수 없음을 뜻한다. (이 경우엔 break로 연쇄 반응을 멈추도록 해야 한다.)
• 위 경우에 해당하지 않는다면 해당 지뢰를 터뜨릴 수 있음을 뜻하기 때문에, 그에 인접한 지뢰에도 충격을 가하는 연산을 수행할 수 있도록 power의 값을 현재 bomb의 값으로 갱신하고 현재 위치의 bomb값을 -1로 설정하여 이미 터진 지뢰임을 표시해 두도록 한다.

 

9) 8)의 연산을 모두 완료하였다면, sort()를 통하여 result의 요소들을 오름차순 정렬한다.

(문제에, 직접 터뜨려야 하는 지뢰의 번호들을 오름차순으로 나열하여 출력할 것이 명시되어 있다.)

 

10) 반복문으로 result의 값에 하나씩 접근하고, 개행으로 값을 구분 지어가며 하나씩 정답을 출력하도록 한다.

위 연산이 모두 완료되었다면 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 2232번 코드
bool compare(pair<int, int> a, pair<int, int> b) {
	return a.second > b.second;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;

	vector<int> bomb;
	vector<pair<int, int>> bomb_sort;
	bomb.push_back(-1);

	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;

		bomb.push_back(num);
		bomb_sort.push_back({ i, num});
	}
	bomb.push_back(-1);
	sort(bomb_sort.begin(), bomb_sort.end(), compare);

	vector<int> result;
	for (int i = 0; i < n; i++) {
		int loca = bomb_sort[i].first;
		int p = bomb_sort[i].second;
		if (bomb[loca] == -1) { continue; }

        bomb[loca] = -1;
		result.push_back(loca);

		int power = p;
		for (int j = 1; true; j++) {
			if (bomb[loca + j] == -1 || power <= bomb[loca + j]) { break; }

			power = bomb[loca + j];
			bomb[loca + j] = -1;
		}
		power = p;
		for (int j = 1; true; j++) {
			if (bomb[loca - j] == -1 || power <= bomb[loca - j]) { break; }

			power = bomb[loca - j];
			bomb[loca - j] = -1;
		}
	}
	
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << endl;
	}
}

 

제출 결과

(2024.05.25 백준 2232번 문제 제출 결과)