[ 백준 ] 2961 도영이가 만든 맛있는 음식 - JavaScript

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

 

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

 

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

 

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

 

입출력 예시

입력

4
1 7
2 6
3 8
4 9

 

출력

1

 

 

 

---

 

 

풀이

'use strict';
const fs = require('fs');

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');
const N = Number(input.shift());

const element = [];
input.forEach(flavor => {
  element.push(flavor.split(' ').map(Number));
});

let diff = 1000000000;

const graph = Array.from({ length: N }, () => []);

for (let i = 1; i < N; i++) {
  for (let j = i; j < N; j++) {
    graph[i - 1].push(j);
  }
}

function updateDiff(sour, bitter) {
  const tempDiff = Math.abs(sour - bitter);
  if (tempDiff < diff) diff = tempDiff;
}

function dfs(v, sour, bitter) {
  updateDiff(sour, bitter);
  if (graph[v].length === 0) return;

  for (let node of graph[v]) {
    dfs(node, sour * element[node][0], bitter + element[node][1]);
  }
}

element.forEach((flavor, index) => dfs(index, flavor[0], flavor[1]));

console.log(diff);

 

신맛과 쓴맛의 차이가 가장 적은 조합을 찾으려면, 모든 조합을 직접 계산해보는 수밖에 없습니다.

 

즉, 이 문제는 완전탐색으로 풀어야 합니다. 저는 이 조합을 구하기 위해 DFS(깊이 우선 탐색) 를 활용했습니다.

 

제 아이디어는 먼저 1을 시작으로 모든 경우의 수를 탐색하는 그래프 구조를 만드는 것이었습니다.

 

1을 선택한 상태에서 나올 수 있는 모든 조합을 탐색한 뒤, 그다음에는 2를 시작으로 하는 조합을,

또 그다음에는 3, 4... 이런 식으로 각 재료를 시작점으로 하여 가능한 모든 조합을 탐색하려는 구조였습니다.

 

이렇게 하면 각 재료를 선택한 경우부터 시작해서 만들 수 있는 모든 경우의 수를 순차적으로 완전 탐색할 수 있다고 생각했습니다.

 

 

1. graph 배열을 이용해 트리 형태 구성

const graph = Array.from({ length: N }, () => []);
for (let i = 1; i < N; i++) {
  for (let j = i; j < N; j++) {
    graph[i - 1].push(j);
  }
}

사진처럼, 각 노드(재료 번호)에서 자기보다 큰 인덱스를 자식으로 연결해서 트리 형태의 조합 그래프를 만들었습니다.

 

2. 각 재료를 시작점으로 DFS 수행

element.forEach((flavor, index) => dfs(index, flavor[0], flavor[1]));

각 재료를 한 번씩 시작 노드로 삼아 해당 재료를 포함한 조합을 모두 탐색합니다.

 

3. DFS로 신맛 * 곱셈, 쓴맛 + 덧셈 누적하며 차이 갱신

function dfs(v, sour, bitter) {
  updateDiff(sour, bitter);
  if (graph[v].length === 0) return;

  for (let node of graph[v]) {
    dfs(node, sour * element[node][0], bitter + element[node][1]);
  }
}

재귀적으로 다음 재료를 선택하면서 신맛은 곱하고, 쓴맛은 더해가며 모든 가능한 조합을 탐색합니다.