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

백준 2138 전구와 스위치

풀이

그리디적으로 만약 목표 상태와 현재 상태가 다를 경우, 스위치를 누릅니다. 이때, 스위치를 최소한으로 누르기 위해 이미 지나온 스위치를 다시 누르지 않도록 해야 합니다. 즉, 1 ~ N번 순서대로 스위치를 누를지 말지 판별합니다.

만약, i번째 스위치를 누를 때 현재 i번 전구와 목표 상태의 i번 전구가 다른지 비교하고 스위치를 누른다면 i - 1번 전구 상태가 변화하면서 목표 상태에 도달하지 못할 가능성이 생깁니다. 이럴 경우, 처음부터 다시 전구의 상태를 비교해줘야 하는 일이 발생합니다.
이런 문제를 방지하지 위해서 i번째 스위치를 누를 때는 i - 1번 전구의 상태를 비교한 후, 다를 경우 i번째 스위치를 누르도록 하였습니다.

i - 1이 존재하지 않는 i = 1을 위해 1번 스위치를 누르고 시작하는 경우와 누르지 않고 시작하는 경우를 나누어 greedy 함수를 실행하였습니다.

코드

const fs = require('fs')
const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'
let input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim())

let [N, initial, goal] = input
let str = initial
let result = Infinity
let count = 0
function toggle(idx) {
  if (str[idx] === '0') str = str.slice(0, idx) + '1' + str.slice(idx + 1)
  else str = str.slice(0, idx) + '0' + str.slice(idx + 1)
}

function greedy() {
  for (let i = 1; i < N; i++) {
    if (str[i - 1] !== goal[i - 1]) {
      count += 1
      toggle(i)
      toggle(i - 1)
      if (i !== N - 1) {
        toggle(i + 1)
      }
    }
  }
  if (str === goal) result = Math.min(result, count)
}

// 초기 상태와 목표가 같다면 0 출력
if (initial === goal) {
  console.log(0)
} else {
  // 1번 스위치를 누르고 시작
  count = 1
  toggle(0)
  toggle(1)
  greedy()

  // 1번 스위치를 누르지 않고 시작
  str = initial
  count = 0
  greedy()

  if (result === Infinity) console.log(-1)
  else console.log(result)
}