[STUDY] 백트래킹 알고리즘 문제풀이 3 (BackTracking Algorithm) 231019

1. 외판원 순회 2

https://www.acmicpc.net/problem/10971

강의에서 제시한 문제 해결 아이디어

• 외판원 순회(traveling salesman problem. TSP) 문제이다.
• 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아와야 한다.
  -> 어떤 노드에서 출발해도 무관

정답 예시

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

let n = Number(input[0]);
let graph = []; // 전체 그래프(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(11).fill(false); // 방문처리 배열
let result = []; // 순열 정보 배열
let minValue = 1e9;

dfc(arr, 0);
console.log(minValue);

// 2부터 N까지의 수를 하나씩 골라 나열하는 모든 순열을 계산
function dfs(arr, 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; // 이동 불가능하면 무시
    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;
  }
}

2. 조합 - 도영이가 만든 맛있는 음식

https://www.acmicpc.net/problem/2961

강의에서 제시한 문제 해결 아이디어

• 모든 길이에 대한 가능한 모든 조합을 구하는 것

정답 예시

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;

function dfs(depth, start) {
  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();
  }
}
dfs(0, 0);
console.log(answer);

3. 로또

https://www.acmicpc.net/problem/6603

강의에서 제시한 문제 해결 아이디어

• 모든 조합을 고려해서 모든 조합을 출력하는 정도로 이해해도 무관

정답 예시

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

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

function dfs(result, depth) {
  if (depth == 6) { // 모든 조합을 확인하는 부분(로또는 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; // [중복x] 이미 처리 된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    visited[i] = true; // 방문 처리
    dfs(arr, depth + 1, i + 1); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
    selected.pop(); // 현재 원소 선택 취소
    visited[i] = false; //방문 처리 취소
  }
}