문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1

20
7
23
19
10
15
25
8
13

예제 출력 1

7
8
10
13
19
20
23

나의 코드

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

// 답을 찾고 나면 true로 바꿀 예정인 변수 선언
let isEnd = false;
// 깊이 우선 탐색에 필요한 visited 빈 배열 선언
let visited = [...Array(9)].map(() => 0);
let ans = [];

function dfs(depth, sum) {
// 리프노드가 있는 깊이 7까지 탐색을 마쳤는데 합이 100이라면?
  if (depth === 7 && sum === 100) {

  // visited에서 1이라고 표시된 인덱스는 input으로 주어진 난쟁이 배열의 인덱스를 의미하므로 ans에 push
    visited.forEach((n, i) => {
      if (n === 1) ans.push(input[i]);
    });
    // 오름차순 정렬
    ans.sort((a, b) => a - b);
    // 답 출력
    ans.forEach((v) => console.log(v));
    // 답 출력 후 더 이상의 탐색이 필요 없으므로 isEnd를 true로 바꿈
    isEnd = true;
  }

// 깊이 우선 탐색하는 for문
  for (let i = 0; i < 9; i++) {
  // 이미 답을 출력한 이후이거나, 이번 경로에서 방문한 노드인 경우 continue
    if (isEnd || visited[i]) continue;

   // 방문 처리
    visited[i] = 1;
    // 한 깊이 내려감, 이번 레벨에서의 노드를 경로의 합인 sum에 합산하여 재귀 호출
    dfs(depth + 1, sum + input[i]);
    
    // 재귀 호출이 완료되면 다시 0으로 바꾼다.
    visited[i] = 0;
  }
}

dfs(0, 0);

브루트포스.. 어렵지만 하나씩 하나씩 해내고 있다~~~!!!

이 문제에서는 깊이가 7인 트리를 완전탐색한다고 생각하고 문제를 풀었다.

9명의 난쟁이가 있다고 문제에서 주어졌으므로 visited 배열의 원소의 개수는 9이고 모두 0으로 초기화하여 시작한다. 깊이 우선 탐색을 할 때 다음 레벨에서의 노드를 현재까지의 합산값인 sum에 더해서 재귀 호출을 한다. 그리고 깊이가 7이 되었을 때 sum이 100이라면 오름차순 정렬 이후 답을 출력한다. 이 떄 이미 답을 출력한 이후이므로 더 이상의 깊이 우선 탐색이 필요하지 않지만, 끝났다고 처리해주지 않으면 재귀호출을 계속한다. 그래서 isEnd라는 변수에 초기에 false를 할당했다가, 답을 출력하고나면 isEnd에 true를 재할당한다. 그리고 for문에 진입하는 조건문에 isEnd를 명시해주고, isEnd가 true라면 이미 답을 반환한 이후이므로 계속 continue만 하게 한다.

++ 오늘 드디어 백준 티어 골드가 되었다!!

🎉🎉🎉🎉🎉
색깔이 금색으로 바뀌니까 뭔가 기분이 좋다 ㅎㅎㅎ 하지만 골드라고 하기에는 부끄러운 실력이라는 걸 내가 제일 잘 안다 흑흑흑ㅠㅠㅠ 또 문제 풀러가야지 짜이찌앤~~~