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

들어가며..

이전에 문제 풀기에 실패했던 2138번 문제를 다시 보고 풀어보았고 결국 답을 보고 어떻게 해결해야하는지 찾아보고 해결하였다.

문제 : https://www.acmicpc.net/problem/2138

본론

알고리즘 선택

완전탐색 DFS

처음에 문제를 보고 어떤 풀이법이나 정공법이 떠오르지 않았다.

그래서 먼저, 완전 탐색을 고려해보았다.

백트래킹을 활용해서, 최대한 가지치기로 속도를 높여보려고 했다.

public static void DFS(char[] before, boolean[] visit, int now, int depth){
    if(depth >= min) return;

    if(isEqualsArr(before)){
        min = Math.min(min, depth);
    }

    for(int i=now; i<before.length; i++){
        if(!visit[i]){
            visit[i] = true;
            takeOn(before, i);
            DFS(before, visit, i+1, depth + 1);
            takeOn(before, i);
            visit[i] = false;
        }
    }
} 

그리디

• 그리디라고는 생각을 못해보았고, 답을 보고 방식을 알게되었다.

설명

그리디 알고리즘은 “현재 위치에서 가장 최선의 선택!”을 통해 탐색한다.

현재 위치에서라는 말이 통용되기 위해서 스위치 문제에서는, 이전 값의 비교를 통해 현재 위치의 버튼을 누를지 말지를 정한다.

왜냐하면, 현재 위치의 버튼을 누르는 것이 i-1, i, i+1의 위치에 영향을 주기 때문에 이전 위치를 기준으로 버튼을 누른다.

하지만, 여기서 첫 번째 버튼의 경우에는 기준점이 없다. 따라서 2가지의 조건 모두를 탐색해보아야 한다.

1번 인덱스부터 차례대로 끝까지 돌면서, i-1번의 상태가 목표 전구와 동일하지 않다면, 현재 위치의 스위치를 누른다.

결과적으로, 0번 인덱스를 누른 경우, 누르지 않은 경우의 상태에서 출발해 위의 그리디 조건으로 모두 눌러보았을 때, 마지막에 목표와 동일하고 더 작다면 정답이된다.

만약 마지막까지 눌렀을때도 동일하지 않다면, 정답이 존재하지 않게 된다.

예제

000을 010을 목표로 눌러야 한다고 가정한다,

1. 첫번째 버튼을 누른 경우 : 110
2. 첫번째 버튼을 누르지 않은 경우 : 000

조건에 따라 버튼을 누른다.

i = 1

1. ( value[i-1] = 1 ) != ( 목표[i-1] = 0 ) 따라서 버튼을 누른다, ⇒ 001
2. ( value[i-1] = 0 ) == ( 목표[i-1] = 0) 따라서 버튼을 누르지 않는다, ⇒ 000

i = 2

1. ( value[i-1] = 0 ) ≠ ( 목표[i-1] = 1 ) 따라서 버튼을 누른다, ⇒ 010
2. ( value[i-1] = 0 ) ≠ (목표[i-1] = 1) 따라서 버튼을 누른다, ⇒ 011

종료 상태

1. 010
2. 011

이 경우 첫 번째 버튼을 누르지 않은 경우는 정답과 동일하지 않기 때문에 첫 번째 버튼을 누른 경우의 값이 정답이 된다.

→ 즉, 3번 버튼을 눌렀다.

소스코드

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

class Main {
    static char[] after;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String before = br.readLine();
        after = br.readLine().toCharArray();

        char[] firstOn = before.toCharArray();
        char[] firstOff = before.toCharArray();

        takeOn(firstOn, 0);
        int c1 = gridy(firstOn) + 1;
        int c2 = gridy(firstOff);

        boolean on = isEqualsArr(firstOn);
        boolean off = isEqualsArr(firstOff);

        if(!(on || off)){
            System.out.println(-1);
            return;
        }

        if(on && !off){
            System.out.println(c1);
            return;
        }

        System.out.println(c2);
    }

    public static int gridy(char[] value){
        int c = 0;
        for(int i=1; i<value.length; i++){
            if(value[i-1] != after[i-1]){
                takeOn(value, i);
                c++;
            }
        }
        return c;
    }

    public static void takeOn(char[] before, int index){
        if(index - 1 >= 0){
            before[index-1] = before[index-1] == '1' ? '0' : '1';
        }

        if(index + 1 < before.length){
            before[index+1] = before[index+1] == '1' ? '0' : '1';
        }

        before[index] = before[index] == '1' ? '0' : '1';
    }

    public static boolean isEqualsArr(char[] before){
        for(int i=0; i<before.length; i++){
            if(before[i] != after[i]) return false;
        }
        return true;
    }
}