10971 외판원 순회 2

문제

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

출력

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

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

My solution

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다)

어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획

단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)

가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다.

W[i][j] 는 W[j][i]와 다를 수 있다.

모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다.

경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

모든 순열을 만들어서 getSum 함수로 경로의 합을 구한 다음 min을 업데이트했다.

const getSum = arr => {
  let sum = 0;
  for (let i = 0; i < N - 1; i++) {
    // A[arr[i]][arr[i+1] 접근했을 때 0이 나오면 길이 없는 것이므로 경로에서 제외
    if (A[arr[i]][arr[i + 1]] === 0) return Number.MAX_SAFE_INTEGER;
    sum += A[arr[i]][arr[i + 1]];
  }
  sum += A[arr[N - 1]][arr[0]];
  return sum;
};
// pass TC
      solution(`4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0`)
    ).toStrictEqual(35);
    expect(
      solution(`4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0`)
    ).toStrictEqual(4);
  });
      solution(`4
0 5 1 99
99 0 5 1
1 99 0 5
5 1 99 0`)
    ).toStrictEqual(20);
JavaScript
복사

제출시 40%에서 fail이 나왔다.

질문 게시판의 반례들은 모두 통과했기 때문에 어디가 문제인지 알 수 없어서 다른 사람의 풀이를 참고했다.

완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번)

완전 탐색을 순열을 이용하여 문제를 한번 기똥차게 풀어보자 일단 순열의 시간 복잡도는 O(N!) 이라는 것을 알자! https://www.acmicpc.net/problem/10819 주어진 정수의 숫자들의 순서를 순열(next_permutation)을 통해 구하고, 조건문을 통해 가장 큰 값을 구합시드아. 근데 여기서 주의할 점은 처음부터 쫘르르르르륵 구해야 하기 때문에, 그냥 주어진 입력에서 순열을 돌리는 것이아니라, 정렬(sort)을 한다음에 돌려야 처음부터 끝까지 도는 것이다.

https://ikso2000.tistory.com/78

우선 순열로 해결하는 방식은 시간복잡도도 느리다고 한다. 그래서 백트래킹을 사용했다.

① 완전 탐색 + 백트래킹 사용법

DP를 이용하는 것과 큰 차이는 없다고 보는데, 기본적으로 모든 도시를 탐색을 하는 방법이다. 그러나 이미 방문한 경우와 갈 수 없는 경우 및 이전 방문으로 계산된 최소 비용을 넘어서는 경우를 제외하고 탐색한다.

즉, 백트래킹을 이용해 가지치기(Pruning)을 하여 필요한 경우에만 건너서 도시를 탐색하는 방법이다.

visit[0] = true;
visitCnt++;
backtracking(0,0,0);
JavaScript
복사

실행하기 전에 visit배열의 0번째를 방문한 것으로 두고 함수를 호출한다.

순회경로의 비용을 계산할 때 어디부터 방문해도 경로가 같다면 총 비용이 같기 때문에 고정된 하나의 도시에서 시작해서 시간복잡도를 낮추기 위해서다.

https://ikso2000.tistory.com/78

시간 복잡도를 줄일 수 있는 방법이 있는데 잘 생각해보면
1 -> 2 -> 3 -> 4 , 
2 -> 3 -> 4 -> 1 , 
3 -> 4 -> 1 -> 2 , 
4 -> 1 -> 2 -> 3
이 네가지는 모든 같은 경우의 수다. 
그래서 첫번째를 제외한 나머지는 의미가 없는 연산이 된다. 
시작 위치를 고정 시켜도 상관이 없는데 , 1의 위치를 고정 시켜버리자
(순열의 갯수가 1줄어듬 , factorial 기준으로는 엄청나게 효과적인 방법)

// 0번째는 방문처리 후 고정해둠 - 방문처리 안해도 비용 계산에는 영향을 주지 않는다.
visit[0] = true;
backtracking(0, 0, 0, 1);
JavaScript
복사

그래서 함수 호출시 첫 정점으로 start에 0을 넣고(0을 첫 정점으로 잡은 경로만 계산할 것이다.)

current도 0에서 시작하므로 0을 준 다음 호출한다.

let min = Number.MAX_SAFE_INTEGER;
const backtracking = (cost, start, current, depth) => {
  if (depth === N && Weight[current][start] !== 0) {
    // 현재 기준 최솟값과 순회 완료되었을 때의 최솟값을 비교한다.
    min = Math.min(min, cost + Weight[current][start]);
    return;
  }
  // 0번째 고정이므로 i : 1 ~ N-1
  for (let i = 1; i < N; i++) {
    if (!visit[i] && Weight[current][i] !== 0) {
      // 순회 중에 최소값을 넘어가면 순회를 멈춘다.
      if (cost + Weight[current][i] < min) {
        visit[i] = true;
        backtracking(cost + Weight[current][i], start, i, depth + 1);
        visit[i] = false;
      }
    }
  }
};
JavaScript
복사

내부에서는 첫번째를 제외했기 때문에 i : 1 ~ N-1까지 for문을 돌면서 방문처리해서 재귀호출한다.

이때 에지케이스 처리가 중요한데, 방문하지 않은 i번째 인덱스이면서 이동할 수 있는 길이 있어야 한다.(Weight[current][i] ≠ 0)

이 조건을 만족하더라도 순회 도중에 최솟값보다 값이 커진다면 순회를 더 진행할 필요가 없다.

	if (depth === N && Weight[current][start] !== 0) {
    // 현재 기준 최솟값과 순회 완료되었을 때의 최솟값을 비교한다.
    min = Math.min(min, cost + Weight[current][start]);
    return;
  }
JavaScript
복사

재귀의 종료조건은 depth가 N이고(N개도시를 방문하고), 현재부터 시작정점(여기서 0)까지의 경로가 존재할 때(Weight[current][start] ≠ 0) 수행된다.

현재 최솟값과 (순회한 경로의 총 비용 + 현재 도시 → 시작 도시의 비용)을 비교해 최솟값을 업데이트한다.

Code

const solution = function (i) {
  const [N, ...Weight] = i
    .toString()
    .trim()
    .split('\n')
    .map((v, i) => (i === 0 ? +v : v.split(' ').map(Number)));
  const visit = [...Array(N)].fill(false);

  let min = Number.MAX_SAFE_INTEGER;
  const backtracking = (cost, start, current, depth) => {
    if (depth === N && Weight[current][start] !== 0) {
      // 현재 기준 최솟값과 순회 완료되었을 때의 최솟값을 비교한다.
      min = Math.min(min, cost + Weight[current][start]);
      return;
    }
    // 0번째 고정이므로 i : 1 ~ N-1
    for (let i = 1; i < N; i++) {
      if (!visit[i] && Weight[current][i] !== 0) {
        // 순회 중에 최소값을 넘어가면 순회를 멈춘다.
        if (cost + Weight[current][i] < min) {
          visit[i] = true;
          backtracking(cost + Weight[current][i], start, i, depth + 1);
          visit[i] = false;
        }
      }
    }
  };
  // 0번째는 방문처리 후 고정해둠 - 방문처리 안해도 비용 계산에는 영향을 주지 않는다.
  visit[0] = true;
  backtracking(0, 0, 0, 1);
  console.log(min);
  return min;
};

describe('외판원순회2', () => {
  it('TC1', () => {
    expect(
      solution(`4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0`)
    ).toStrictEqual(35);
  });
  it('TC2', () => {
    expect(
      solution(`4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0`)
    ).toStrictEqual(4);
  });
  it('TC3', () => {
    expect(
      solution(`4
0 5 1 99
99 0 5 1
1 99 0 5
5 1 99 0`)
    ).toStrictEqual(20);
  });
});
JavaScript
복사