백준 14939번 불 끄기 자바스크립트

같이 코테문풀하시는 분이 카카오 코테 문제를 들고 오셔서,, 단체로 문제 난이도가 올라갔다^^

행복

---

 

일단 저번 스도쿠 문제도 비슷한 방식이었기 때문에, 2차원 배열로 만들어주고 내부는 boolean값으로 매핑해주었다.

 

일단 true를 만나면, 앞뒤위아래로 하나씩 체크해보면서 만약 있으면 해당 위치로 이동하고 이동해서 최대로 끌 수 있는 만큼 끄고, 다시 true를 탐색하는 방식으로 접근했다.

function change2DArray(input) {
  return input.split('\n').map(row => row.split('').map((el)=> el === '0'));
}

function toggleAroundSwitch(x, y, array) {
  if (x >= 0 && x < 10 && y >= 0 && y < 10) {
    array[x][y] = !array[x][y];
  }
  if (x >= 0 && x < 10 && y - 1 >= 0 && y - 1 < 10) {
    array[x][y - 1] = !array[x][y - 1]; // left
  }
  if (x >= 0 && x < 10 && y + 1 >= 0 && y + 1 < 10) {
    array[x][y + 1] = !array[x][y + 1]; // right
  }
  if (x - 1 >= 0 && x - 1 < 10 && y >= 0 && y < 10) {
    array[x - 1][y] = !array[x - 1][y]; // top
  }
  if (x + 1 >= 0 && x + 1 < 10 && y >= 0 && y < 10) {
    array[x + 1][y] = !array[x + 1][y]; // bottom
  }
}

function checkArray(array) {
  for (let x = 0; x < 10; x++) {
    for (let y = 0; y < 10; y++) {
      if (array[x][y]) return false; 
    }
  }
  return true;
}

function cacluateCount(array) {
  let minCount;
  
  for (let i = 0; i < 2**(10*10); i++){
    let copiedArray = array.map(row => row.slice());
    let count = 0;

    for (let x = 0; x < 10; x++) {
      if (x === 0) {
        for (let y = 0; y < 10; y++) {
          if (copiedArray[x][y]) {
            toggleAroundSwitch(x, y, copiedArray);
            count++;
          }
        }
      }
    
      else {
        for (let y = 0; y < 10; y++) {
          if (copiedArray[x][y]) {
            toggleAroundSwitch(x, y, copiedArray);
            count++;
          }
        } 
      }
    
      if (checkArray(copiedArray)) {
        minCount = Math.min(minCount, count);
      }
    }
  }

  return !minCount ? -1 : minCount;
}

const input = `#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#`

console.log(cacluateCount(change2DArray(input)))

 

 

일단 모든 케이스를 고려하면서, 한번씩 토글을 눌렀을 때 모든 값이 false가 나오지 않거나, 이전의 값이 더 크면 끝나는 방식으로 계산하였다. 처음에는 모든 케이스를 고려하는게 10 * 10만 되면 된다고 생각했는데, 이걸 모든 케이스를 계산하려면 실제로 2**100의 케이스가 생겼다...?

---

 

일단 알고리즘을 보면 그리디 알고리즘, 브루트포스 알고리즘, 비트마스킹이 있다. 그리고 나는 세 개 다 모른다..

그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 각 단계에서 최적의 선택을 하며 최종적으로 가장 좋은 선택을 통해 답을 구하는 방식이다.

브루트포스 알고리즘(Brute Force Algorithm)

부루트포스 알고리즘은 가능한 모든 경우의 수를 시도해보는 방식으로 문제를 해결하는 방식이다. 다만 경우에 따라 시간복잡도 혹은 공간 복잡도가 너무 커질 수 있다.

비트마스킹(Bitmasking)

비트마스킹은 컴퓨터 과학에서 비트 연산을 이용하여 부분 집합을 나타내거나 상태를표현하는 기법이다. 주로 집합의 부분 집합을 나타내는데 사용되며, 각 비트가 특정 원소의 포함 여부를 나타낸다.   

---

감도 안 잡혀서, 결국 답을 참고할 수밖에 없었다. 답변을 비교하고 재구성하면서 코테를 풀 때 다른 사람들은 어떻게 구현하는지 팁을 얻을 수 있었다.

function change2DArray(input) {
  return input.trim().split('\n').map(row => row.split('').map(el => el === 'O' ? 1 : 0));
}

function toggleAroundSwitch(array, y, x) {
  const y_index_list = [0, 0, 1, 0, -1];
  const x_index_list = [0, 1, 0, -1, 0];

  for (let i = 0; i < 5; i++) {
    let current_y = y + y_index_list[i];
    let current_x = x + x_index_list[i];
    if (current_y >= 0 && current_y < 10 && current_x >= 0 && current_x < 10) {
      array[current_y][current_x] = (array[current_y][current_x] + 1) % 2;
    }
  }
}

 

이 케이스 같은 경우는 x와 y가 변경될 좌표들을 배열에 담고 반복해서 조건문을 하나로 통일해서 사용할 수 있었다.

function calculateCount(board) {
  let firstLinePressCase = new Array(1 << 10).fill(101);

  for (let caseNum = 0; caseNum < (1 << 10); caseNum++) {
    let tmpBoard = board.map(row => row.slice());
    let count = 0;

    let mask = 1;
    for (let j = 9; j >= 0; j--) {
      if (caseNum & mask) {
        toggleAroundSwitch(tmpBoard, 0, j);
        count++;
      }
      mask <<= 1;
    }

    for (let i = 1; i < 10; i++) {
      for (let j = 0; j < 10; j++) {
        if (tmpBoard[i - 1][j] === 1) {
          toggleAroundSwitch(tmpBoard, i, j);
          count++;
        }
      }
    }

    if (tmpBoard[9].every(val => val === 0)) {
      firstLinePressCase[caseNum] = cnt;
    }
  }

  let answer = Math.min(...firstLinePressCase);
  return answer === 101 ? -1 : answer;
}

const input = `#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#`;

const board = change2DArray(input);
console.log(calculateCount(board));

 

먼저 첫번째 줄에서 나올 수 있는 케이스를 계산한다. 10개의 요소가 두 가지 상태를 가질 수 있으므로 1024개이다. 그리고 첫번째 줄의 모든 케이스에서 각각 두번째 열로 넘어가서 현재 위치의 한 칸 위의 전구가 켜져있으면 현재 위치의 전구를 통해 주변의 전구를 켜게 된다. 마지막 줄까지 다 확인해서, 맨 마지막 줄에 전구 켜진게 없으면 성공이고, 아닐 경우 -1을 가진다. 각각의 케이스마다 전구를 켜는 숫자를 세서 최소값을 변경시켜주면 답을 얻을 수 있다.

let firstLinePressCase = new Array(1 << 10).fill(101);

 

<< 는 비트 연산자로, 좌측으로 비트를 이동시키는 연산자이다. 1 << 10은 2의 10승으로 1024이므로, 첫번째 줄의 모든 케이스를 담는, 101()로 채워진 1024 길이의 배열을 선언한다.

function calculateCount(board) {
  let firstLinePressCase = new Array(1 << 10).fill(101);

  for (let caseNum = 0; caseNum < (1 << 10); caseNum++) {
    let tmpBoard = board.map(row => row.slice());
    let count = 0;

    let mask = 1;

 

먼저, 앞에서 만든 첫줄의 모든 케이스를 반복한다. 가장 먼저 받은 배열을 깊은 복사하여 현재 케이스를 구성하고, 현재 케이스의 카운트를 선언한다.

 

mask는 비트마스킹에서 사용될 비트를 나타내며, 초기에는 가장 오른쪽 비트가 설정된다.

for (let j = 9; j >= 0; j--) {
      if (caseNum & mask) {
        toggleAroundSwitch(tmpBoard, 0, j);
        count++;
      }
      mask <<= 1;
    }

 

그리고 첫 줄의 각 요소에 대해 뒤에서부터 계산한다. 현재의 숫자(뒤의 요소부터)와 현재보다 앞의 숫자가 둘 다 켜져있으면 전구를 끈다. 그리고 mask를 <<= 연산자를 통해 왼쪽으로 1만큼 이동시킨다. 

    for (let i = 1; i < 10; i++) {
      for (let j = 0; j < 10; j++) {
        if (tmpBoard[i - 1][j] === 1) {
          toggleAroundSwitch(tmpBoard, i, j);
          count++;
        }
      }
    }

 

그리고 두번째 줄부터는 돌면서 켜져있는 경우 끈다.

    if (tmpBoard[9].every(val => val === 0)) {
      firstLinePressCase[caseNum] = cnt;
    }
  }

  let answer = Math.min(...firstLinePressCase);
  return answer === 101 ? -1 : answer;
}

 

그렇게해서 마지막 줄에 도달했을 때, 모든 전구가 꺼져있으면 배열의 요소를 카운트로 변경하고, 최종적으로 배열에서 가장 최소값을 구하거나 전부 그대로 101인 경우 -1을 반환한다.  

---

최종코드

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

function change2DArray(input) {
  return input.trim().split('\n').map(row => row.split('').map(el => el === 'O' ? 1 : 0));
}

function press(b, y, x) {
  const SIZE = 10;
  const dy = [0, 0, 1, 0, -1];
  const dx = [0, 1, 0, -1, 0];

  for (let i = 0; i < 5; i++) {
    let ny = y + dy[i];
    let nx = x + dx[i];
    if (ny >= 0 && ny < SIZE && nx >= 0 && nx < SIZE) {
      b[ny][nx] = (b[ny][nx] + 1) % 2;
    }
  }
}

function calculateCount(board) {
  const SIZE = 10;
  let firstLinePressCase = new Array(1 << 10).fill(101);

  for (let caseNum = 0; caseNum < (1 << 10); caseNum++) {
    let tmpBoard = board.map(row => row.slice());
    let cnt = 0;

    let mask = 1;
    for (let j = 9; j >= 0; j--) {
      if (caseNum & mask) {
        press(tmpBoard, 0, j);
        cnt++;
      }
      mask <<= 1;
    }

    for (let i = 1; i < SIZE; i++) {
      for (let j = 0; j < SIZE; j++) {
        if (tmpBoard[i - 1][j] === 1) {
          press(tmpBoard, i, j);
          cnt++;
        }
      }
    }

    if (tmpBoard[SIZE - 1].every(val => val === 0)) {
      firstLinePressCase[caseNum] = cnt;
    }
  }

  let answer = Math.min(...firstLinePressCase);
  return answer === 101 ? -1 : answer;
}

let input = '';
rl.on('line', function(line) {
  input += line + '\n';
}).on('close', function() {
  const board = change2DArray(input);
  console.log(calculateCount(board));
});

Reference

https://youtu.be/yHBYeguDR0A?si=N034X7O48JPHj5bf

[python] 백준 14939 : 불 끄기 (velog.io)

[python] 백준 14939 : 불 끄기