[BOJ] 2138 전구와 스위치

1. 문제요약

2138번: 전구와 스위치 (acmicpc.net)

2138번: 전구와 스위치

N개의 스위치와 N개의 전구가 있다. i (1 < i < N) 번 스위치를 누르면 i - 1, i, i + 1 의 세 개의 전구의 상태가 동시에 바뀐다.

(자기 자신을 포함해서 양 옆에 있는 전구가 동시에 바뀐다.) N개의 전구들 현재 상태와 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

2. 문제예제

 

 

3. 팩트추출

Fact 1 : 자기 자신의 스위치를 바꿀 수 있는 것은 양 옆에 있는 전구이다.

그런데 만약 0 ~ N - 1 까지 순차적으로 실행하게 된다면, 왼쪽에 있는 전구는 오른쪽 전구에 의해 바뀔 수 있으므로 사고 과정에서 생략할 수 있다. 오른쪽 전구로만 컨트롤하게 바꾼다면 이전 정보가 필요 없어지게 된다. 또 부분문제이기 때문에 그리디 알고리즘으로 풀 수 있다.

 

Fact 2 : i - 1 번째 전구만 보면서 타겟 전구와 같다면 넘기고, 다르다면 스위치를 누른다. 그런데 가장 첫 번째 전구는 눌러야 할지, 말아야 할지 결정할 수가 없기 때문에 두 가지 경우의 수 모두 구한다.

 

Fact 3 : i 가 마지막 N 위치까지 왔는데 타겟 전구의 상태와 다르다면, 도달할 수 없다는 뜻이고 같다면 최소의 경우의 수 이므로 count 를 반환한다. 이 전략이 항상 최선의 상태를 반환하는지는(최소 값을 보장하는지는) 아래 문제풀이(수동)을 통해 알아본다.

 

4. 문제풀이(수동)

그리디 알고리즘은 해당 전략이 항상 최선의 상태를 반환해주는지 검증해야 한다. 문제를 전구 배열 3 크기로 나누어서 생각해본다.

 

현재 전구 상태 : 010

목표 전구 상태 : 111

 

목표 전구 상태와 다른 부분을 보고 바로 킨다면 010 -> 100 -> 011 루틴으로 가장 첫 번째 전구를 못 키게 된다.

그 다음 인덱스에서 킨다면 101 -> 110 -> 111 로 안정적으로 킬 수 있게 된다.

 

현재 전구 상태 : 000

목표 전구 상태 : 111

 

중간에 있는 전구 하나만 키면 되는 것처럼 보이지만 그 다음 인덱스에서 키기 때문에 이 중간 문제도 해당 공식이 성립한다. 이처럼 3 전구 상태 배열의 모든 경우의 수를 나열하고 테스트 해보았을 때, 오른쪽에 있는 전구를 킬 때가 가장 올바른 선택이라는 것을 알 수 있다.

 

5. 문제전략

문제 전략은 예제 풀이(수동)과 팩트 추출을 통해 알아보았다.

 

6. 소스코드

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

public class Main {
    static int N;
    static char lightArray[][], targetArray[];
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lightArray = new char[2][N];
        lightArray[0] = br.readLine().toCharArray();
        lightArray[1] = br.readLine().toCharArray();
        targetArray = br.readLine().toCharArray();
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    private static void run(int index, int count, int type) {
        if(index == N) {
            if(lightArray[type][index-1] == targetArray[index-1]) {
                answer = Math.min(answer, count);
            }
            return;
        }
        if(lightArray[type][index-1]!=targetArray[index-1]) {
            push(index,type);
            run(index+1,count+1,type);
        } else {
            run(index + 1, count, type);
        }
    }
    private static void push(int index, int type) {
        for(int i=index-1; i<=index+1; i++) {
            if(i>=0 && i<N)
                lightArray[type][i] = lightArray[type][i] == '1' ? '0' : '1';
        }
    }
}