[JAVA] 백준 알고리즘 2138번 (전구와 스위치)

문제

---

이번에 다뤄볼 문제는 2138번 문제 ' 전구와 스위치'입니다.

문제에서 연습해야 하는key-point는 그리디 알고리즘 입니다.

 

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법입니다.

예를들어 'A도시에서 B도시까지 이동 할 때, 총 5개의 지점을 꼭 거쳐서 가야하며 이때의 최소 이동거리를 구하시오.' 라는 요구사항이 있다면 그리디 알고리즘을 사용할 경우 현재의 지점에서 가장 가까운 지점으로 이동을 하며 최종 결과를 도출해내는 알고리즘이라 생각하면 됩니다.

 

단, 여기서 주의해야 할 부분은 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 합니다.

 

그럼 이제 문제를 살펴보겠습니다.

문제에서는 총 N개의 전구가 주어지고 이 전구들을 최종적으로 원하는 상태로 변경하는데 필요한 스위치 사용의 최소값을 결과로 출력하길 원하고 있습니다. 이 문제는 스위치의 성격(on/off)으로 인해 매 순간의 선택이 최적의 선택이 될 수 있기 때문에 그리디 알고리즘을 사용하는것이 가능 합니다. 

 

우선 문제의 예제로 주어진 상황을 통해 먼저 어떤 로직을 도출해야 하는지 알아보겠습니다.

주어진 전구는 3개이며 초기 상태는 000, 최종 원하는 상태는 010 입니다. 즉, 가운데 전구만 켜져있는 모습을 원하고 있습니다.

그럼 전구의 상태 000을 010으로 바꾸는 과정을 살펴보도록 하겠습니다.

전구 1, 2, 3을 각각 진행하며 스위치를 매번 사용하면 총 3번의 스위치 사용으로 원하는 결과를 얻을 수 있는 모습을 볼 수 있습니다.

여기서 "전구 2 스위치 사용" 부분에 집중 해보겠습니다. 우리는 전구 2에서 왜 스위치를 사용해야한다고 생각했을까요? 그건 N-1위치에 있는 전구1의 상태가 1이기 때문에 전구2에서 스위치를 사용하여 전구1의 상태를 최종 원하는 상태인 0으로 바꾸고 다음 단계로 넘어가야 한다는걸 알 기 때문입니다. 

 

우리는 N개의 전구를 앞에서부터 순차적으로 훑어나가며 N번째에서 스위치를 사용했을때 N-1, N, N+1 총 3개의 전구가 영향을 받게 된다는 것을 알고 있습니다. 즉, 위 예제를 통해 우리는 N번째에서 N-1 전구의 상태를 최종적(변하지 않는 값)으로 결정 내릴 수 있다는걸 알 수 있습니다.

 

그렇다면 순서대로 진행하며 현재 내 순서 바로 이전의 전구 상태를 확정짓는다고 했을때 첫번째 전구는 어떻게 처리 할 수 있을까요? 처음 시작할때부터 키고 진행해야 하는지, 끄고 진행해야 하는지 알 수가 없습니다. 따라서 첫번째 전구의 스위치를 사용한 케이스와 사용하지 않은 케이스 모두에 대해 고려해야합니다. 

그러므로 아래 코드에서 givenArrayTypeA, givenArrayTypeB로 주어진 현재 전구 상태를 두개로 나눠놓은 이유는 바로 첫번째 전구의 스위치를 사용하고 시작하는 경우와 사용하지 않고 시작하는 경우 두가지 모두를 진행하기 위함입니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

이렇게 첫번째 전구를 키고 사용한 경우와 그렇지 않은 경우 모두를 탐색하며 두가지 방식 중 스위치 사용 횟수에 대한 최소값을 구하면 문제를 해결하게 됩니다. 단, 원하는 최종 전구 상태를 만들지 못할 경우 -1을 출력하라고 했기 때문에 이 부분을 고려해서 아래와 같이 코드를 작성하면 됩니다.

---

코드(JAVA)

import java.util.Scanner;

public class Main {

    static int n;
    static int answer = Integer.MAX_VALUE;
    static boolean[] goalArray;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        String given = sc.next();
        String goal = sc.next();

        boolean[] givenArrayTypeA = new boolean[n];
        boolean[] givenArrayTypeB = new boolean[n];
        goalArray = new boolean[n];

        for (int i = 0; i < n; i++) {
            givenArrayTypeA[i] = given.charAt(i) != '0';
            givenArrayTypeB[i] = given.charAt(i) != '0';
            goalArray[i] = goal.charAt(i) != '0';
        }

        // 첫번째 전구 스위치 사용하지 않고 진행
        greedyChoice(1, 0 , givenArrayTypeA);
        // 첫번째 전구 스위치 사용하고 진행
        greedyChoice(1, 1 , usingSwitch(0, givenArrayTypeB));

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    static void greedyChoice(int index, int count, boolean[] givenArray) {
        if (index == n) {
            if (givenArray[index - 1] == goalArray[index - 1]) {
                answer = Math.min(answer, count);
            }
            return;
        }

        if (givenArray[index - 1] != goalArray[index - 1]) {
            greedyChoice(index + 1, count + 1, usingSwitch(index, givenArray));
        } else {
            greedyChoice(index + 1, count, givenArray);
        }
    }

    static boolean[] usingSwitch(int index, boolean[] givenArray) {
        for (int i = index - 1; i <= index + 1; i++) {
            if (i >= 0 && i < n) {
                givenArray[i] = !givenArray[i];
            }
        }
        return givenArray;
    }
}

 

2138번: 전구와 스위치