백트래킹 문제풀이(3)

7. 외판원 순회 2(10971)

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

작성한 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0]); // 도시의 수
let graph = [];
for (let i = 0; i <= n; i++) graph.push([0]);
for (let i = 1; i <= n; i++) {
  line = input[i].split(" ").map(Number);
  for (let j = 0; j < n; j++) graph[i].push(line[j]);
}

let visited = new Array(n+1).fill(false); // 방문 여부
let result = [];
let minValue = 1e9;

dfs(0);
console.log(minValue);

// 2부터 N까지의 수를 하나씩 골라 나열하는 모든 순열 계산
function dfs(depth) {
  // 현재 순열에 대한 처리
  if (depth == n - 1) {
    let totalCost = 0; // 1번 노드에서 출발
    let cur = 1; // 1번 노드에서 출발
    // 현재 순열에 따라서 노드 이동
    for (let i = 0; i < n - 1; i++) {
      let nextNode = result[i]; // 다음 이동 노드까지의 비용 계산
      let cost = graph[cur][nextNode];
      if (cost == 0) return; // 이동 불가능하면 무시
      totalCost += cost; // 이동 가능하면, 비용을 더하고 노드 이동
      cur = nextNode;
    }
    // 마지막 노드에서 1로 돌아오는 것이 필수
    let cost = graph[cur][1];
    if (cost == 0) return 1; // 이동 불가능하면 무시
    totalCost += cost; // 이동 가능하면, 비용 더하고 노드 이동
    minValue = Math.min(minValue, totalCost); // 경로의 최소 비용 저장
  }
  for (let i = 2; i <= n; i++) {
    if (visited[i]) continue;
    result.push(i); // 방문 처리
    visited[i] = true;
    dfs(depth + 1); // 재귀 함수 호출
    result.pop(); // 방문 처리 해제
    visited[i] = false;
  }
}

풀이

• 어떤 노드에서든지 출발해도 괜찮음 → 1번 노드부터 시작한다고 정해놓고 풀이
• 마지막 노드에서 1번 노드로 돌아오는 경우도 포함!

---

8. 도영이가 만든 맛있는 음식(2961)

문제

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

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

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

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

입력

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

출력

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

작성한 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = [];
// 각 재료의 (신맛, 쓴맛) 기록
for (let i = 1; i <= n; i++) {
  let [x, y] = input[i].split(" ").map(Number);
  arr.push([x, y]);
}
let visited = new Array(n).fill(false); // 방문 처리 배열
let result = [];
let answer = 1e9;

dfs(0, 0);
console.log(answer);

function dfs(depth, start) {
  // 현재 조합에 대하여 결과 계산
  // 모든 길이에 대한 조합을 구하는 것이므로 1 이상이면 모두 실행
  if (depth >= 1) {
    let totalX = 1; // 신맛(곱)
    let totalY = 0; // 쓴맛(합)
    // 인덱스 하나씩 확인하며
    for (let i of result) {
      let [x, y] = arr[i];
      totalX *= x;
      totalY += y;
    }
    answer = Math.min(answer, Math.abs(totalX - totalY));
  }
  // 모든 조합 계산
  for (let i = start; i < n; i++) {
    if (visited[i]) continue;
    visited[i] = true; // 방문 처리
    result.push(i);
    dfs(depth + 1, i + 1); // 재귀 함수 호출
    visited[i] = false; // 방문 처리 해제
    result.pop();
  }
}

풀이

• 모든 길이에 대한 가능한 모든 조합을 구하는 것
• ex) 재료로 A, B, C, D 네 가지 존재
  • 길이 1: (A), (B), (C), (D)
  • 길이 2: (A, B), (A, C), (A, D), (B, C), (B, D), (C, D)
  • 길이 3: (A, B, C), (A, B, D), (A, C, D), (B, C, D)
  • 길이 4: (A, B, C, D)

---

9. 로또(6603)

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

작성한 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let line = 0;
let visited = [];
let selected = [];
let answer = "";

while (1) {
  let arr = input[line].split(" ").map(Number);
  if (arr[0] == 0) break; // 테스트 케이스 종료 조건
  let n = arr[0];
  arr = arr.slice(1);
  visited = new Array(n).fill(false); // 각 원소 인덱스 별 방문 여부
  selected = []; // 현재 조합에 포함된 원소
  answer = "";
  dfs(arr, 0, 0);
  console.log(answer);
  line++;
}

function dfs(arr, depth, start) {
  // 모든 조합을 확인하는 부분(로또는 6개의 자연수로 구성)
  if (depth == 6) {
    let result = []; // 조합 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 조합을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  // start 지점부터 하나씩 원소 인덱스 확인
  for (let i = start; i < arr.length; i++) {
    if (visited[i]) continue; // 중복 허용하지 않으므로 이미 처리된 원소라면 무시
    visited[i] = true; // 방문 처리
    selected.push(i); // 선택
    dfs(arr, depth + 1, i + 1); // 재귀 함수 호출 시 다음 인덱스 넣기
    selected.pop(); // 선택 해제
    visited[i] = false; // 방문 취소
  }
}

풀이

• k개에서 6가지 숫자 선택하는 문제 → $kC6$
• 오름차순으로 정렬해야 하므로 start 변수 필요