백준 3088 - 화분 부수기 (자바 - 그리디)

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

3088번: 화분 부수기

 

* 문제 요약

화분 N개를 놓았다. 이 화분을 모두 부수어 버리려고 한다. 화분은 한 줄로 놓여져 있으며, 세 정수가 쓰여져 있다.

화분 하나를 깼을 때, 그 화분에 쓰여있는 숫자와 오른쪽에 있는 임의의 화분에 쓰여있는 숫자가 하나라도 겹친다면 해당하는 화분은 깨진다.

이것은 연쇄적으로 일어난다. 따라서 화분 하나만 깨서 모든 화분을 깰 수 있다.

되도록 적은 수의 화분을 직접 깨서 모든 화분을 깨지게 만들려고 한다. 이때 직접 깨야하는 화분의 최소 갯수를 구하는 프로그램을 작성하시오.

위의 그림에서 2번 화분을 깬다면, 3번과 4번 화분은 숫자 2가 겹치기 때문에 화분이 깨지며, 숫자 9가 겹치기 때문에 화분 5가 깨지게 된다. 이제 남은 화분은 1번이기 때문에 1번만 깨면 모든 화분을 깰 수 있다.

즉, 화분 2개를 직접 깨서 모든 화분을 깰 수 있는것이다.

 

* 입력

첫째 줄에 화분의 갯수 N이 주어진다. (1 <= N <= 300,000)

다음 N개 줄에는 각 화분에 쓰여있는 숫자 3개 Ai, Bi, Ci 가 놓여져 있는 순서대로 주어진다. (1 <= Ai, Bi, Ci <= 1,000,000)

 

* 출력

첫째 줄에 직접 깨야하는 화분 갯수의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

처음엔 int 형 2차원 배열에 항아리에 적힌 숫자들을 열 단위로 저장한 다음 길이가 1,000,001 인 boolean 배열에 깨진 항아리에 적혀있는 숫자를 true 로 바꿔주며, 매 탐색마다 겹치는 숫자의 인덱스 값이 true 이면 항아리를 직접 깨는 횟수를 늘리지 않고, 만약 항아리에 적혀있는 숫자 3개의 인덱스 값이 모두 false 이면 직접 항아리를 깨는 횟수를 1 늘리면서 3개 숫자의 인덱스 값을 true 로 바꿔주었었다.

 

그런데 이후에 생각해보니 굳이 입력값들을 먼저 받아서 2차원 배열에 저장한 다음, 이걸 다시 이용하려고 할 필요 없이 입력받는 순간 곧바로 boolean 배열에 항아리에 적혀있는 숫자의 인덱스 값이 true 인지 false 인지 확인하면 되겠다는 판단이 들어 2차원 배열을 활용하지 않고 항아리에 적혀있는 숫자들을 입력받는 순간 곧바로 처리하게끔 로직을 작성했다.

 

매 반복 단계마다 현재 입력받은 항아리에 적힌 숫자를 인덱스로 하였을 때, boolean 배열에서 해당하는 인덱스의 값이 하나라도 true 인 경우 이미 앞에서 깨진적이 있는 항아리와 적혀있는 숫자가 겹친다는 뜻이므로 항아리를 직접 깨는 횟수를 늘리지 않고,

만약 항아리에 적혀있는 숫자에 해당하는 인덱스 값이 모두 false 라면 앞에서 겹치는 숫자가 적힌 항아리가 깨진적이 없다는 뜻이므로 항아리를 직접 깨는 횟수를 1 증가시켜준다.

 

앞에서 겹치는 숫자가 존재해서 이미 깨져있는 항아리든, 조건에 해당되지 않아서 직접 깨야하는 항아리든 매 탐색때마다 발견한 항아리는 반드시 깨지는 상황이 기본이므로 항아리에 적혀있는 숫자에 해당하는 인덱스를 모두 true 로 변경시켜준다.

 

* 코드

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 size = Integer.parseInt(br.readLine());
        boolean[] breakArray = new boolean[1000001];
        int result = 0;

        for (int i = 0; i < size; i++) {
            String[] input = br.readLine().split(" ");
            int number1 = Integer.parseInt(input[0]);
            int number2 = Integer.parseInt(input[1]);
            int number3 = Integer.parseInt(input[2]);

            if (!breakArray[number1] && !breakArray[number2] && !breakArray[number3]) {
                result++;
            }
            breakArray[number1] = true;
            breakArray[number2] = true;
            breakArray[number3] = true;
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에 최적의 해답을 선택한다. -> 뒤에 올 입력과는 관계없이 현재 입력받은 숫자가 boolean 배열의 인덱스 상에서 하나라도 true 인지, 또는 모두 false 인지에 따라 항아리를 직접 깨는 횟수를 늘릴지 줄일지 결정한다.

선택한 해답이 조건을 만족하는지 검사한다. -> 모든 항아리에 적혀있는 숫자들의 입력상태를 확인하기 전까지는 항아리를 직접 깨는 횟수가 최소치에 최대한 가까워졌다고 할 수 없으므로 모든 입력에 대해 로직이 수행될때까지 반복을 계속한다.

 

위의 과정을 통해 직접 항아리를 깨는 횟수의 최솟값을 알아냈으므로 그리디 알고리즘에 해당된다.