백준 js 10971번

<문제>

 

 

<문제 핵심>

1. 이번 문제도 마찬가지로 먼저 노트에 트리 구조로 각 도시들을 그려 본 다음 문제를 진행하였다. 노트에 그려본 구조는 다음과 같다. selected 배열을 만들었고 1번 도시부터 시작하는 경우는 selected = [1, 2, 3, 4] 로 배열이 채워질 것이다.그리고 depth가 n과 같아지면, 즉 모든 도시를 탐색했다면 백트래킹이 적용되어 위에 있는 2번 도시 부터 탐색을 시작하게 될것!

 

2. 시작 지점에서 도착 지점으로 갈 수 없는 경우의 예외처리를 해줬어야 했다.(푸는 과정에서 누락해버림)

 

<문제 풀이과정 및 순서도>

1. 입력받은 다음 방문했는지를 확인하기 위한 visited 배열, 선택된 도시들을 담는 selected 배열을 생성한다. 

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input.shift();
let cities = input.map((city) => city.split(" ").map(Number));
let visited = Array.from({ length: n + 1 }, () => false); //[false, false. false. false, false]
const list = [];
let selected = [];

 

 

2.  dfs 재귀 로직을 구현한다.

✅ 밑에 반복문을 통해 방문하는 도시를 선택하고 selected 배열에 삽입한다. 해당 과정이 진행되며 이후 모든 도시를 탐색했다면 비용을 계산하고 리스트에 추가한다. 예외처리는 두 가지를 해야하는데 첫 번째는 비용 계산 시 도착 도시가 없으면 첫 번째 도시로 돌아오도록 설정 해야한다. 두 번째는 두 도시 간에 경로가 없을 경우 해당 경로를 무시하고자 return을 통해 예외처리 해준다.

✅ list의 요소들 중 최소값을 출력한다.

const dfs = (depth) => {
  if (depth === n) {
    let result = 0;
    for (let i = 0; i < n; i += 1) {
      let start = selected[i]; //출발하는 도시
      let end = selected[i + 1]; //도착하는 도시
      //맨 마지막 도시인 경우, 맨 처음 도시로 가는 경로 설정
      if (end === undefined) end = selected[0];

      //i에서 j로 가는 길이 있을 경우 result에 누적해준다.
      if (cities[start][end] !== 0) {
        result += cities[start][end];
      } else return;
    }
    list.push(result);
    return;
  }

  for (let i = 0; i < n; i += 1) {
    if (visited[i]) continue; //방문했던 도시 제외
    visited[i] = true;
    selected.push(i);
    dfs(depth + 1);
    selected.pop();
    visited[i] = false;
  }
};

dfs(0);
const answer = Math.min(...list); //경우의 수들 중에서 가장 작은 값
console.log(answer);

 

<전체 코드>

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input.shift();
let cities = input.map((city) => city.split(" ").map(Number));
let visited = Array.from({ length: n + 1 }, () => false); //[false, false. false. false, false]
const list = [];
let selected = [];

const dfs = (depth) => {
  if (depth === n) {
    let result = 0;
    for (let i = 0; i < n; i += 1) {
      let start = selected[i]; //출발하는 도시
      let end = selected[i + 1]; //도착하는 도시
      //맨 마지막 도시인 경우, 맨 처음 도시로 가는 경로 설정
      if (end === undefined) end = selected[0];

      //i에서 j로 가는 길이 있을 경우 result에 누적해준다.
      if (cities[start][end] !== 0) {
        result += cities[start][end];
      } else return;
    }
    list.push(result);
    return;
  }

  for (let i = 0; i < n; i += 1) {
    if (visited[i]) continue; //방문했던 도시 제외
    visited[i] = true;
    selected.push(i);
    dfs(depth + 1);
    selected.pop();
    visited[i] = false;
  }
};

dfs(0);
const answer = Math.min(...list); //경우의 수들 중에서 가장 작은 값
console.log(answer);