[백준] 2138번 전구와 스위치(JAVA)

문제

- N개의 스위치와 N개의 전구

- i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀜

- 현재 상태와 만들고자 하는 상태가 주어졌을때, 그 상태를 만들기 위해 스위치를 최소 몇 번 눌러야 하는지 출력

- 불가능한 경우 -1 출력

 

해결방법

각 전구의 최종 상태는 다음 스위치에 따라 달라진다. 즉, 1번 전구는 2번 스위치를 누르냐, 누르지 않느냐에 따라 최종 상태가 결정된다.

따라서, 이전 전구 상태를 확인하면서 스위치를 눌러 상태를 만들어가는 식으로 문제를 해결하였다.

// 예시로 4개의 전구가 주어지고 현재 상태는 0001, 만들고자 하는 상태는 1001인 경우를 보겠다.
4
0001
1001

1. 첫 전구의 켜고 끈 경우로 나누어 스위치를 누르도록 진행하였다.

2. 두 번째 스위치를 누르면 첫 번째, 두 번째, 세 번째의 전구가 영향을 받는다. 첫 번째 전구는 두 번째 스위치로 최종 상태가 결정되기 때문에 A, B 각각에서  첫 번째 전구의 상태를 보고 두 번째 스위치를 누를지 말지를 결정해야 한다.

위 사진에서 볼 수 있듯이 A는 1번 전구가 만들고자하는 상태와 같고, B는 1번 전구가 만들고자하는 상태와 다르다. 그러므로 B만 두 번째 스위치를 켜주면된다.

 3. 세 번째 스위치를 누르면 두 번째, 세 번째, 네 번째의 전구가 영향을 받는다. 두 번째 전구는 세 번째 스위치로 최종 상태가 결정되기 때문에 A, B 각각에서 두 번째 전구의 상태를 보고 세 번째 스위치를 누를지 말지를 결정해야 한다.

2번 사진에서 볼 수 있듯이 A와 B의 2번 전구 모두 만들고자하는 상태와 다르다. 그러므로 A, B 모두 세 번째 스위치를 켜줘야 된다.

4. 네 번째 스위치를 누르면 세 번째, 네 번째의 전구가 영향을 받는다. 세 번째 전구는 네 번째 스위치로 최종 상태가 결정되기 때문에 A, B 각각에서 세 번째 전구의 상태를 보고 네 번째 스위치를 누를지 말지를 결정해야 한다.

3번 사진에서 볼 수 있듯이 A는 3번 전구가 만들고자하는 상태와 다르고, B는 3번 전구가 만들고자하는 상태와 같다. 그러므로 A의 네 번째 스위치를 켜준다.

마지막 스위치까지 누르고 나면, 만들고자하는 상태와 같은 A 경우를 확인할 수 있다. 이때, 스위치를 누른 횟수가 3번이므로 최종적인 답은 3이 출력되어야 한다.

 

처음 이 방식으로 코드를 짜고 채점하였을 때, 100%까지 갔다가 틀렸습니다가 나오는 경우를 확인하였다. 무엇이 문제인지 감이 잡히지 않아 한참동안 고민을 많이 했는데, 나는 스위치 하나씩 바꿀 때마다 현재 A와 B의 상태를 만들고자하는 상태와 비교하였고, 그 때 같은 경우가 있다면 바로 횟수를 출력하고 프로그램을 종료하는 방식으로 코드를 작성했었다. 

하지만, 만약 해당 차례에 A와 B가 모두 만들고자하는 상태와 같다면 더 적은 횟수로 스위치를 누른 경우를 출력했어야 했다. 따라서 중간에 두 상태가 같다면 더 적은 횟수를 출력할 수 있도록 조건을 만들어 문제를 해결하였다.

 

코드

import java.io.*;
import java.util.*;

public class Main{
    static int N;
    static boolean[] now, want, nowA, nowB;		// 현재 상태, 만들고자하는 상태, A, B
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        now = new boolean[N];
        want = new boolean[N];

        switchState(br.readLine(), now);
        switchState(br.readLine(), want);

        nowA = new boolean[N];    // 1번 스위치 켠 상태
        nowB = new boolean[N];    // 1번 스위치 끈 상태

        int switchA = 1, switchB = 0;	// 처음 1번 스위치에 대해 A는 킨 상황이므로 1로 시작

	// 1번 스위치 켜고 끈 상태를 각 nowA, nowB 배열에 저장
        for(int i = 0; i<N; i++){
            if(i <= 1){
                nowA[i] = !now[i];
                nowB[i] = now[i];
            }else{
                nowA[i] = now[i];
                nowB[i] = now[i];
            }
        }

	// 스위치를 하나씩 탐색
        for(int i = 1; i<N; i++){
            // 이전 전구가 만들고자하는 상태와 같지 않다면 스위치를 켜줘야 함
            if(nowA[i-1] != want[i-1]){
                switchOn(i, nowA);
                switchA++;
            }
            if(nowB[i-1] != want[i-1]){
                switchOn(i, nowB);
                switchB++;
            }
			
            // 스위치를 켜고 나서 A, B 배열이 만들고자하는 상태와 같은지 비교하여 출력
            if(Arrays.equals(nowA, want)){
            	// A, B가 둘 다 만들고자하는 상태와 같을 땐, 더 적은 횟수 출력
                if(Arrays.equals(nowA, nowB)){
                    System.out.println(Math.min(switchA, switchB));
                    System.exit(0);
                }
                System.out.println(switchA);
                System.exit(0);
            } else if (Arrays.equals(nowB, want)) {
                System.out.println(switchB);
                System.exit(0);
            }
        }
        // 끝까지 모두 탐색하였으나 불가능한 경우에는 -1 출력
        System.out.println(-1);
    }

    // 스위치 켜는 함수
    static void switchOn(int i, boolean[] switchName){
        switchName[i-1] = !switchName[i-1];
        switchName[i] = !switchName[i];
        // 마지막 스위치는 다음 전구가 없으므로 조건을 걸어줌
        if(i<N-1){
            switchName[i+1] = !switchName[i+1];
        }
    }
	
    // 스위치 상태를 입력 받는 함수
    static void switchState(String state, boolean[] switchName){
        for(int i = 0; i<N; i++){
            char n = state.charAt(i);
            if(n == '1'){
                switchName[i] = true;
            }else if(n == '0'){
                switchName[i] = false;
            }
        }
    }
}