[백준 14927] 전구 끄기 (C#, C++) - soo:bak

작성일 :

문제 링크

14927번 - 전구 끄기

설명

격자의 한 칸을 누르면 그 칸과 상하좌우 칸의 전구 상태가 반전됩니다. 모든 전구를 끄기 위해 필요한 최소 클릭 횟수를 구하는 문제입니다.


접근법

이 문제의 핵심은 첫 번째 줄에서 어떤 칸을 누를지 결정하면, 나머지 줄의 행동이 자동으로 결정된다는 점입니다.


첫 줄을 처리한 후 두 번째 줄로 넘어갑니다. 이때 첫 줄에 아직 켜진 전구가 있다면 반드시 꺼야 합니다. 그런데 두 번째 줄의 어떤 칸을 누르면 그 바로 위 칸이 반전됩니다. 따라서 첫 줄의 켜진 전구를 끄려면 그 바로 아래 칸을 눌러야 합니다. 선택의 여지가 없습니다.


같은 논리가 모든 줄에 적용됩니다. 두 번째 줄을 처리한 후 세 번째 줄에서는 두 번째 줄의 켜진 전구를 끄기 위해 해당 위치를 눌러야 합니다. 이렇게 마지막 줄까지 내려갑니다.


마지막 줄까지 처리한 후 마지막 줄의 모든 전구가 꺼져 있으면 성공입니다. 마지막 줄에 켜진 전구가 남아 있다면 그 첫 줄 가정으로는 모든 전구를 끌 수 없다는 뜻입니다.


첫 줄에서 누를 칸의 조합은 2의 N승 가지입니다. 모든 조합을 시도하면서 각각에 대해 위 과정을 수행하고, 모든 전구를 끌 수 있는 경우 중 최소 클릭 횟수를 찾습니다. 한 줄의 상태를 비트마스크로 표현하면 토글 연산을 효율적으로 처리할 수 있습니다.


Code

C#

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
50
51
52
53

using System;

class Program {
  const int INF = int.MaxValue;
  static int n;

  static void Press(int[] board, int r, int c) {
    var bit = 1 << (n - c - 1);
    board[r] ^= bit;
    if (r > 0) board[r - 1] ^= bit;
    if (r + 1 < n) board[r + 1] ^= bit;
    if (c > 0) board[r] ^= 1 << (n - c);
    if (c + 1 < n) board[r] ^= 1 << (n - c - 2);
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    var origin = new int[n];
    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      for (var j = n - 1; j >= 0; j--)
        if (parts[n - 1 - j] == "1") origin[i] |= 1 << j;
    }

    var answer = INF;
    var limit = 1 << n;
    for (var mask = 0; mask < limit; mask++) {
      var board = new int[n];
      Array.Copy(origin, board, n);
      var cnt = 0;

      for (var c = 0; c < n; c++) {
        if ((mask & (1 << c)) != 0) {
          Press(board, 0, c);
          cnt++;
        }
      }

      for (var r = 1; r < n; r++) {
        for (var c = 0; c < n; c++) {
          if ((board[r - 1] & (1 << (n - c - 1))) != 0) {
            Press(board, r, c);
            cnt++;
          }
        }
      }

      if (board[n - 1] == 0 && cnt < answer) answer = cnt;
    }

    Console.WriteLine(answer == INF ? -1 : answer);
  }
}

C++

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
50
51
52
53
54
55
56

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

const int INF = 0x3f3f3f3f;
int n;

void press(vi& v, int r, int c) {
  v[r] ^= 1 << (n - c - 1);
  if (r) v[r - 1] ^= 1 << (n - c - 1);
  if (r + 1 < n) v[r + 1] ^= 1 << (n - c - 1);
  if (c) v[r] ^= 1 << (n - c);
  if (c + 1 < n) v[r] ^= 1 << (n - c - 2);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  vi orig(n);
  for (int i = 0; i < n; i++) {
    for (int j = n - 1; j >= 0; j--) {
      int x; cin >> x;
      if (x) orig[i] |= 1 << j;
    }
  }

  int ans = INF;
  int limit = 1 << n;
  for (int mask = 0; mask < limit; mask++) {
    vi board = orig;
    int cnt = 0;

    for (int c = 0; c < n; c++) if (mask & (1 << c)) {
      press(board, 0, c);
      cnt++;
    }

    for (int r = 1; r < n; r++) {
      for (int c = 0; c < n; c++) {
        if (board[r - 1] & (1 << (n - c - 1))) {
          press(board, r, c);
          cnt++;
        }
      }
    }

    if (board[n - 1] == 0) ans = min(ans, cnt);
  }

  cout << (ans == INF ? -1 : ans) << "\n";

  return 0;
}

이 블로그의 다른 글