백준/2138 전구와 스위치

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 전구와 스위치 문제는 비트마스크 연산으로 구현한다.

  • Backtracking으로 앞에서부터 비교하며 모든 경우를 확인한다.
  • 스위치를 누르는 과정을 XOR 연산을 활용하면 스위치를 켜고 끄는 구현을 편하게 할 수 있다.
  1. 첫 번째 스위치를 누르고 시작하는 경우 / 누르지 않고 시작하는 경우 로 나눠 시작한다.
  2. 두 번째 스위치부터 n-1 번째 스위치 값과 비교한다.
    1. input[n-1] == target[n-1] 이라면 스위치를 누르지 않는다.
    2. input[n-1] != target[n-1] 이라면 스위치를 누른다.
    3. (총 길이 - 1) 번째 까지 반복한다.
  3. (총 길이 - 1) 에 접근 시 스위치를 누를 때 / 누르지 않을 때를 비교한다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static char[] input, target;
    public static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        input = br.readLine().toCharArray();
        target = br.readLine().toCharArray();
        Backtracking(1, 0);
        input[0] ^= 1;
        input[1] ^= 1;
        Backtracking(1, 1);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }

    public static void Backtracking(int idx, int cnt) {
        if (idx == input.length - 1) {
            // n-1번째 스위치를 누르지 않아도 같은 경우
            if (input[idx] == target[idx] && input[idx - 1] == target[idx - 1]) {
                ans = Math.min(ans, cnt);
                return;
            }
            // n-1번째 스위치를 누르면 같아지는 경우
            if ((input[idx] ^ 1) == target[idx] && (input[idx - 1] ^ 1) == target[idx - 1]) {
                ans = Math.min(ans, cnt + 1);
                return;
            } else return;
        }
        if (input[idx - 1] == target[idx - 1])  //idx-1번째 스위치가 같으면 스위치를 누를 필요 없다.
            Backtracking(idx + 1, cnt); 
        else {
            //idx번째 스위치 누른 경우
            input[idx] ^= 1;
            input[idx - 1] ^= 1;
            input[idx + 1] ^= 1;
            Backtracking(idx + 1, cnt + 1);
            input[idx] ^= 1;
            input[idx - 1] ^= 1;
            input[idx + 1] ^= 1;
        }
        return;
    }
}