백준_전구 길만 걷자_17359

전구 길만 걷자

문제

선린 친구들은 ✨인기스타 슈퍼인싸 예원쌤✨을 존경한다. 방학 동안 선생님을 뵐 수 없다니! 그래서 학생들은 방학식 날 💡전구 길만 걷자💡라는 엄청난 이벤트를 준비했다.

💡💡💡💡👨‍🏫💡💡💡💡

아무도 몰랐지만, 사실 선린의 과학실에는 전구가 일렬로 이어진 전구 묶음이 N개 있다. 학생들은 이 묶음을 일렬로 이어 전구 길을 만들기로 했다. 하지만 묶음에는 불이 들어오지 않는 전구가 섞여 있었는데, 전구들을 일렬로 이어 놓으니 켜진 전구와 꺼진 전구가 번갈아 나타나서 전구 길이 예쁘지 않았다.

그래서 학생들은 전구 길이 최대한 예쁘도록 묶음을 배열하려고 한다. 전구 길은 전구 상태가 바뀌는 횟수가 최소일 때 가장 예쁘다고 한다. 이는 켜진 전구를 1, 꺼진 전구를 0이라 했을 때, 전구 길에 01 또는 10이 최소로 나타나야 한다는 의미이다.

예를 들어, (1011) 묶음과 (1000) 묶음을 이어 붙여야 한다고 하자. 이때는 (10111000) 순서로 잇는 것이 (10001011) 순서로 잇는 것보다 예쁘다. 전자는 전구의 상태가 3번 바뀌고, 후자는 전구의 상태가 4번 바뀌기 때문이다.

그런데 갑자기 세한이가 코드를 작성해서 이를 계산하자고 한다.

세한이와 함께 전구 길을 예쁘게 꾸며보자!

입력

첫째 줄에 전구 묶음의 개수 N이 주어진다. (1 ≤ N ≤ 10)

둘째 줄부터 N개의 줄에 걸쳐, 각 줄마다 전구 묶음의 상태를 나타내는 문자열이 주어진다. 문자열은 0 또는 1로만 이루어져 있으며 0은 꺼진 전구를, 1은 켜진 전구를 의미한다.

문자열의 길이는 1 이상 100 이하이다.

출력

전구 묶음을 가장 예쁘게 배치했을 때, 전구의 상태가 바뀌는 횟수를 출력한다.

예제 입력 1

3
11100
0000101
011100

예제 출력 1

6

예제 입력 2

4
00
01
10
11

예제 출력 2

2

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = +input[0]; // 전구 묶음의 개수
const listOfBulb = []; // 전구 묶음의 각 전구의 앞과 뒤
let changeCnt = 0; // 이어 붙이지 않았을 때 전구의 변경 횟수
for (let i = 1; i < N + 1; i += 1) {
  const blubs = input[i].split('');
  blubs.reduce((prev, blub, idx) => {
    if (idx > 0 && prev !== blub) changeCnt += 1;
    return blub;
  }, blubs[0]);
  listOfBulb.push([+blubs[0], +blubs.at(-1)]);
}

const visited = new Array(N).fill(false);
let count = Number.MAX_SAFE_INTEGER;
const backtracking = (depth, prev, cnt) => {
  if (depth === N) count = Math.min(count, cnt);

  for (let i = 0; i < N; i += 1) {
    if (!visited[i]) {
      visited[i] = true;
      backtracking(
        depth + 1,
        listOfBulb[i][1],
        // 이어붙였을 때 앞의 전구의 맨 뒤와 같지 않으면 전구 횟수 카운트 증가
        cnt + (prev !== listOfBulb[i][0] ? 1 : 0)
      );
      visited[i] = false;
    }
  }
};

backtracking(0, -1, -1);
console.log(changeCnt + count);

풀이 및 해설

• 전구 상태 바뀌는 횟수가 최소일 때의 변경 횟수 (1≤N≤10)
  1. 먼저, 각 전구의 변경 횟수 카운트
  2. 각 전구의 맨 앞과 맨 뒤 저장 후, 백트래킹 이용하여 앞 전구의 맨 뒤와 같은지 비교