백준 2232 - 지뢰 (자바 - 그리디)

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

2232번: 지뢰

 

* 문제 요약

일직선상에 N 개의 지뢰가 같은 간격으로 매설되어 있다. 각각의 지뢰는 충격강도 Pi 가 있어서, Pi 를 초과하는 힘을 가라면 Pi 만큼의 힘을 발휘하며 터지게 된다.

어떤 지뢰가 터지게 되면 그 지뢰의 좌우에 있는 지뢰에 힘을 발휘하게 된다.

 

예를 들어 다음과 같이 지뢰가 매설된 경우를 보자.

1 2 5 4 3 3 6 6 2

첫번째의 지뢰를 터뜨리게 되면 두번째 지뢰에 1 만큼의 힘을 발휘하게 된다. 만약 세번째의 지뢰를 터뜨리게 되면 2, 4번째 지뢰에 5만큼의 힘을 발휘하게 된다. 따라서 2, 4번째 지뢰도 연쇄반응을 일으키며 터지고, 다시 1번 지뢰에 2만큼의 힘을, 5번 지뢰에 4만큼의 힘을 발휘하며 연쇄반응을 일으킨다.

그 후에는 6번 지뢰에 3만큼의 힘을 가하게 되고, 이는 3을 초과하는 힘이 아니기 때문에 연쇄반응이 멈추게 된다.

정리하면, 세번째의 지뢰를 직접 터뜨리고 나면 1 ~ 5번 지뢰가 모두 터지게 된다. 다음으로 7, 8번 지뢰를 각각 터뜨리면 모든 지뢰를 터뜨릴수 있다.

 

지뢰를 직접 터뜨리는 것은 위험하기 때문에, 당신은 최소 갯수의 지뢰를 직접 터뜨려서 모든 지뢰를 터뜨리려 한다.

위의 예시에서는 세 개의 지뢰를 직접 터뜨리면 연쇄반응에 의해서 모든 지뢰를 터뜨릴 수 있다.

각 지뢰에 대한 정보가 주어졌을 때, 최소 갯수의 지뢰를 직접 터뜨려서 모든 지뢰를 터뜨리고자 할 때, 직접 터뜨려야 하는 지뢰들을 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 N이 주어진다.

다음 N개의 지뢰는 차례대로 각 지뢰의 충격강도 Pi 가 주어진다.

 

* 출력

직접 터뜨려야 하는 지뢰의 번호를 오름차순으로 출력한다.

 

* 제한

- 1 <= N <= 50,000

- 1 <= Pi <= 10,000

 

* 예시

 

* 해결 과정

입력받은 지뢰들의 순서를 기준으로 첫번째 인덱스의 경우 자신의 바로 뒤에 입력으로 들어오는 지뢰의 충격강도와 비교해서 직접 터뜨릴지 그냥 넘어갈지 결정하고, 마지막 인덱스의 경우 자신의 앞에 입력으로 들어온 지뢰의 충격강도와 비교해서 직접 터뜨릴지 그냥 넘어갈지 결정한다.

처음과 마지막 인덱스가 아닌 중간에 온 인덱스의 경우 자신의 앞과 뒤에 입력으로 들어와 있는 지뢰 2개와 충격강도를 비교하여, 둘 보다 충격강도가 더 크다면 직접 터뜨린다.

 

매 반복마다 뒤에 들어올 지뢰가 어떻냐와 관계없이 현재 탐색 기준으로 위와 같이 로직을 설계할 수 있는 이유는, 어차피 위의 3가지 조건에 맞지 않는 지뢰들은 직접 터뜨리지 않아도 주위의 지뢰가 터지는 것으로 인해 연쇄적으로 터지는것이 확정적이기 때문이다.

그렇기 때문에 지뢰가 연쇄적으로 터질 때 이 연쇄반응이 어디까지 가는지는 고려할 필요가 없다.

 

위의 3가지 조건을 만족하지 않는 지뢰가 어떻게 될 지 한번 자세히 생각해보자.

첫번째 조건, 처음에 가장 먼저 들어온 지뢰가 바로 뒤에 입력으로 들어온 지뢰의 충격강도 보다 큰 경우.

이 조건을 만족하지 않으면 가장 처음에 들어온 지뢰가 바로 뒤에 입력으로 들어온 지뢰보다 충격강도가 작다는 뜻인데, 이렇게 되면 가장 처음에 들어온 지뢰는 그 다음에 들어올 지뢰가 터지기만 해도 확정적으로 연쇄반응으로 함께 터지게 된다.

 

두번째 조건도 마찬가지, 가장 마지막에 들어온 지뢰의 충격강도가 자신의 바로 앞에 입력으로 들어온 지뢰보다 충격강도가 작은 경우, 자신의 바로 앞에 입력으로 들어온 지뢰가 터질때 연쇄적으로 함께 터지게 된다.

 

세번째 조건의 경우도 자신의 앞, 뒤 어느곳이든 자신보다 충격강도가 더 큰 지뢰가 들어온다면 둘 중 어느 한 지뢰가 터질때 확정적으로 함께 터진다.

즉, 3가지 조건 모두 만족되지 못하는 지뢰의 경우 조건을 만족하는 지뢰가 발견되어 직접 터뜨린 지뢰 때문이든, 앞이나 뒤에서 터진 지뢰 때문에 연쇄적으로 터진 지뢰 때문이든, 반드시 연쇄반응으로 인해 터지게 된다는 뜻이다.

 

탐색을 계속 진행하다보면 반드시 3가지 조건 중 하나를 만족해서 직접 터뜨려야 하는 지뢰가 발견된다. 그로인해 그 지뢰의 앞이나 뒤에 존재하는 조건을 만족하지 못하는 지뢰들은 모두 연쇄적으로 터지게 된다.

오름차순 출력의 경우 어차피 입력받은 지뢰를 처음부터 순서대로 탐색하며 조건을 만족하는 지뢰가 발견되면 그 즉시 출력하기 때문에 따로 정렬과 같은 과정을 거칠 필요가 없다.

 

+ 각 조건에서 >=, <= 연산자가 붙은 이유는 다음과 같다.

1. 자신의 앞이나 뒤에 자신보다 충격강도가 작은 지뢰가 있을 경우 직접 터뜨려서 해당 지뢰들을 연쇄적으로 터뜨리기 위함

2. 자신의 앞이나 뒤에서 연쇄반응이 끝나 자신 혼자만 덩그러니 남겨지게 되는 경우 해당 지뢰를 직접 터뜨려줘야 하기 때문

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        int[] mineArray = new int[count];

        for (int i = 0; i < count; i++) {
            mineArray[i] = Integer.parseInt(br.readLine());
        }

        if (count == 1) {
            bw.write(1 + "\n");
        } else {
            for (int i = 0; i < mineArray.length; i++) {
                if (i == 0) {
                    if (mineArray[i] >= mineArray[i + 1]) {
                        bw.write((i + 1) + "\n");
                    }
                }
                else if (i == mineArray.length - 1) {
                    if (mineArray[i] >= mineArray[i - 1]) {
                        bw.write((i + 1) + "\n");
                    }
                }
                else {
                    if (mineArray[i] >= mineArray[i - 1] && mineArray[i] >= mineArray[i + 1]) {
                        bw.write((i + 1) + "\n");
                    }
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 현재 탐색중인 지뢰가 자신의 앞이나 뒤에 있는 지뢰보다 충격강도가 더 큰 경우 해당 지뢰를 직접 터뜨려서 충격강도가 상대적으로 작은 지뢰들을 연쇄적으로 터뜨린다.

선택된 해답이 조건을 만족하는지 검사한다. -> 입력된 모든 지뢰를 탐색해야만 조건을 만족하는 최적해에 가장 가까운 값을 찾을 수 있으므로 입력받은 지뢰들을 처음부터 끝까지 모두 탐색을 진행한다.

 

위의 과정을 통해 직접 터뜨려야 하는 지뢰의 최소 갯수를 찾아낼 수 있었으므로 그리디 알고리즘 문제에 해당된다.