abonglog최근 DFS,BFS 추천문제들을 살펴보다가 우연히 외판원 순회문제를 보게 되었고 너무나도 이해가 안가서 이것 저것 블로그들을 살펴보며, 공부하며 글을 작성해본다.
문제 소개
해당 문제는 2차원 평면 위에 N개의 지점들이 존재하고 각 위치들이 서로 연결 되어있다고 가정한다. (전부 연결되어 있을 수도, 연결되어 있지 않을 수도 있다.)
이 때 i 도시에서 j 도시까지 가는 경로에 걸리는 비용을 저장하는 2차원 자료구조 W 가 있을 때 모든 도시를 순회하면서 비용을 최소화 하는 경로를 구하는 문제이다.
예를 들어 W[i][j] 는 i 도시부터 j 도시까지 이동 할 때의 비용을 의미하며 W[i][j] 와 W[j][i] 는 서로 다를 수 있다. (만약 W[i][j] 가 0이라면 i 도시에서 j 도시까지 가는 경로가 존재하지 않음을 의미한다.)
내 설명이 너무 중구난방인거 같아 나무위키에 정의된 설명을 함께 첨부한다. 훨씬 이해하기 쉽게 정리된 문구인거 같다.
주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾아라.
외판원 순회 문제는 NP 난해 문제에 속한다.
P-NP 문제의 정의와 P = NP
우선 NP 난해 문제란 것이 무엇인지 알아보기 전 다항 시간 (Polynomial time) 만에 해결되는 문제가 무엇인지 알아보자
다항 시간이란 것은 복잡도 관점에서 데이터 개수 N 개 크기에 따라 올라가는 복잡도의 수준이 O(N), O(N ** k), O (N log N) 수준에 풀리는 문제들을 의미 한다.
이정도 수준은 데이터 개수가 커질 때에도 비교적 빠른 시간 내에 해결이 가능한 문제들을 의미 한다.
하지만 다항 시간만에 풀리지 않는 문제들은 O(k ** N) 이나 O(N!) 와 같은 복잡도를 가지는 문제들을 의미한다.
const factorial = (n)=>{
if (n === 0){
return 1;
}
return n * factorial(n-1)
}
factorial(20) // 2432902008176640000 비 다항시간만에 풀리는 문제의 경우 데이터의 크기가 20개만 되어도 O(N!) 의 경우 무려 2432902008176640000 번의 연산이 필요하다.
1초에 한 번에 연산이 있다고 가정해도 771억년이나 필요하고 우주의 나이보다 오래 걸린다고 한다. 와우
문제들의 집합을 의미하는 P, NP , NP 난해 , NP 완전 문제에 대해 알아보자
- P (Polynomial time, Easy to Solve) : 다항 시간만에 풀이가 가능한 문제
P 문제는 결정적 알고리즘으로 계산의 각 단계에서 한 가지의 가능성만을 고려하여 알고리즘을 다항 시간만에 풀 수 있는 문제들을 의미한다.
- NP (Non-deterministic Polynomial time , Easy to Check) : 답을 다항 시간에 찾는 것은 어렵지만 정답이 있을 때 정답의 옳고 그름을 다항시간만에 찾기 쉬운 문제 를 의미한다.
NP 문제는 문제를 푸는 동안 여러 가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘으로 다항 시간에 문제를 해결하지 못하는 문제를 의미 한다.
하지만 풀이에 대한 정답이 주어졌을 때 다항 시간만에 확인하는 것이 가능한 문제들을 의미 한다.
- NP 난해 문제 : 모든 NP 문제들을 다항식 시간 내에 환원 할 수 있는 문제
NP 난해 문제는 매우 어려운 문제이지만 이 문제를 다항 시간 내에 해결하는 방법을 발견한다면 NP 집합에 있는 모든 문제 풀이 방법에 적용해 NP 문제들을 해결 할 수 있는 문제 를 의미 한다. NP 난해 문제들은 항상 NP 문제 집합에 포함되는 것은 아니다. (정답을 확인하는 것이 다항 시간안에 푸는 것이 불가능 할 수 있다.)
- NP 완전 문제 : NP 난해이면서 동시에 NP 문제
NP 완전 문제는 NP 문제이면서 NP 문제인 것을 의미 한다. 즉 정답을 찾는 것은 오래 걸리지만 확인하는것은 다항 시간만에 풀 수 있으며 정답을 찾는 방법을 다항 시간만에 발견한다면 모든 NP 문제들을 다항 시간만에 풀 수 있는 문제들을 의미한다.
P = NP
P = NP 문제란 NP 문제가 있을 때 NP문제는 다항 시간만에 정답이옳고그름을 확인 할 수 있으니 해결 방법도 다항 시간만에 찾을 수 있지만 아직 우리가 모르는 것이 아닌가? 하는 문제이다.
현재 P = NP 인지 NP 가 아닌지에 대한 증명조차 나지 않았으며 해당 문제를 증명하면 100만 달러의 상금을 받을 수 있다고 한다. 와우
외판원 순회 문제
외판원 순회문제 이미지
외판원 순회문제는 N 개의 경로를 모두 이동하고 다시 출발점으로 돌아오는 가장 빠른 경로를 찾는 문제이며 NP 난해 문제에 해당한다.
왜 ?
- i 번째 도시에 도착 했을 때 아직 도착하지 않은 경로들의 경우의 수를 고려해야하기 때문에 비결정적 알고리즘이다. (NP)
- 어떤 경로 X가 주어졌을 때 해당 경로 X의 비용을 찾는 것은 경로별 비용의 총합을 계산하면 되기 때문에 다항 시간안에 해결이 가능하다. (NP)
- 모든 정점을 한 번씩 확인하는 경로가 존재하는지 여부를 묻는 결정 해밀턴 경로 문제 (NP 완전) 의 해결 방안으로부터 환원된 해결 방법을 사용 할 수 있다. (NP 난해)
N 개의 경로에서 존재 할 수 있는 모든 경로의 총합을 계산하는 것은 O(N!) 번이나 걸린다. 모든 가능한 경로의 수가 N! 가 되기 때문이다.
DP 자료구조를 이용하면 O (N ** 2 * 2 ** N) 만에 풀 수 있다. 이도 다항시간을 아득히 뛰어넘는 아주 오랜 시간이지만 N! 에 비하면 양반이라 할 수 있다.
완전 탐색으로 풀어보기 (O(N!))
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0이렇게 각 지점 별 비용이 존재 할 때 가능한 모든 경로의 총합을 계산하고 최소값을 찾아보자
const fs = require("fs");
const path = require("path");
const filePath =
process.platform === "linux"
? "/dev/stdin"
: path.join(__dirname, "input.txt");
const inputs = fs.readFileSync(filePath).toString().trim().split("\n");
const N = +inputs[0];
const W = inputs.slice(1).map((line) => line.split(" ").map(Number));
const findShortestPath = (N, W) => {
let minCost = Infinity;
const visited = Array(N).fill(false);
const dfs = (currentNode, depth, cost) => {
if (depth === N) {
// 모든 노드를 방문한 후 시작점으로 돌아오는 비용 추가
if (W[currentNode][0] !== 0) {
minCost = Math.min(minCost, cost + W[currentNode][0]);
}
return;
}
for (let nextNode = 0; nextNode < N; nextNode++) {
if (!visited[nextNode] && W[currentNode][nextNode] !== 0) {
visited[nextNode] = true;
dfs(nextNode, depth + 1, cost + W[currentNode][nextNode]);
visited[nextNode] = false;
}
}
};
// 시작점을 0으로 고정
visited[0] = true;
dfs(0, 1, 0); // 시작 노드에서 DFS 시작
return minCost;
};
console.log(findShortestPath(N, W));백트래킹 기법을 이용하여 가능한 모든 경로를 탐색하여 최소한의 비용이 드는 minCost 값을 구해주었다.
모든 가능한 경로들을 2차원 배열 형태로 만들려 했더니 공간 복잡도가 N! 이 되어버려 메모리 초과가 떠버리더라
그래서 백트래킹을 이용해 경로를 생성하고 순회한 DFS 트리의 깊이가 N 개가 되면 돌아오는 경로의 비용까지 함께 합쳐주었다.
어차피 어디서 출발하든 순환하는 경로기 때문에 첫 출발지는 어디로 선택하든 결과값은 같다.
예를 들어 어떤 구해진 경로
0 -> 1 -> 2 -> 0이 있다고 가정해보자. 그 순회하는 경로는 0에서 출발하는거로 찾은 경로지만 1에서 출발한 경로인1 -> 2 -> 0 -> 1이 경로와 동일하다.
이 알고리즘의 시간 복잡도는 순회 가능한 모든 연결 그래프 모두를 탐색하기 때문에 O(N!) 이다. (모든 노드들이 연결된 완전 그래프라 가정했을 때)
동적 계획법으로 풀어보기
동적 계획법을 이용해 이전에 구해둔 경로들로 값을 구해 시간 복잡도를 줄여볼 수 있다.
비트 연산자들을 이용해서 풀이하는데 아주 아름다워서 눈물이 콸콸 났다. 여러 블로그글과 강의 영상들, 잼미니를 하루동안 괴롭힌 후 드디어 이해가 됐다.
우선 코드를 먼저 보고 필요한 개념들을 추후 서술한다.
const fs = require("fs");
const path = require("path");
const filePath =
process.platform === "linux"
? "/dev/stdin"
: path.join(__dirname, "input.txt");
const inputs = fs.readFileSync(filePath).toString().trim().split("\n");
const N = +inputs[0];
const W = inputs.slice(1).map((line) => line.split(" ").map(Number));
const findShortestPath = (N, W) => {
// dp[visited][i] = visited 상태이면서 마지막 정점이 i인 경우의 최단 비용 길이
const dp = Array.from({ length: 1 << N }, () => Array(N).fill(Infinity));
dp[1][0] = 0; // 00...001 에서 시작하는 경우 비용은 0
// 가능한 모든 경로 조합을 탐색
// 00...00 (N 비트)에서 시작하여 11...11 (N 비트)까지 모든 visited 상태를 탐색
for (let visitedMask = 0; visitedMask < 1 << N; visitedMask++) {
for (let currentCity = 0; currentCity < N; currentCity++) {
// 현재 탐색하고자 하는 경로에 현재 도시가 포함되어 있지 않으면 skip
if (!((1 << currentCity) & visitedMask)) {
continue;
}
for (let nextCity = 0; nextCity < N; nextCity++) {
// 다음 도시가 이미 방문한 도시라면 skip
if ((1 << nextCity) & visitedMask) {
continue;
}
// 현재 도시에서 다음 도시로 가는 경로가 없다면 skip
if (W[currentCity][nextCity] === 0) {
continue;
}
// 현재 탐색 경로에 netxCity를 추가한 visited 상태
const nextVisitedMask = visitedMask | (1 << nextCity);
const nextVisitedCost =
dp[visitedMask][currentCity] + W[currentCity][nextCity];
// 다음 도시를 방문하는 경우의 비용을 업데이트
dp[nextVisitedMask][nextCity] = Math.min(
dp[nextVisitedMask][nextCity],
nextVisitedCost
);
}
}
}
const minCost = dp[(1 << N) - 1].reduce((acc, cur, index) => {
return Math.min(acc, cur + (W[index][0] || Infinity));
}, Infinity);
return minCost;
};
console.log(findShortestPath(N, W));비트 연산자
코드의 흐름을 이해 하기 전 비트 연산자의 개념에 대해 먼저 알아보고 가자
10진수로 작성되는 모든 수 들은 컴퓨터에선 이진수(bit)로 컴파일 되어 사용 된다는 것을 알고 있을 것이다.
이 때 비트들을 연산하는 비트 연산자들을 알아보자
비트 쉬프트 연산자
비트 쉬프트 연산자는 쉬프트 방향에 따라 << , >> 로 사용되며 a << b 라는 식이 있다면 a 를 b 만큼 좌측으로 쉬프트 하겠다는 것을 의미한다.
>>>처럼 부호 없는 우측 쉬프트 연산자도 있으나 이 부분은 제외한다.
예를 들어 1을 나타내는 비트 000... 001 을 좌측으로 3 만큼 쉬프트 한다면 000...01000 이 된다.
자바스크립트의 값들은 특별한 경우가 아니라면 32비트로 표현된다.
해당 쉬프트 연산자는 a 란 숫자를 2 ** b 만큼 곱하겠다는 것과 같은 의미를 가진다.
이진 비트 연산자
이진 비트 연산자는 비트 or 을 나타내는 |, 비트 and 를 나타내는 & 가 존재한다.
||,&& 는 논리값을 나타내는 이진 논리 연산자라면 이진 비트 연산자는 값을 나타낸다.
a | b 연산자의 경우 각 비트 자리수에 해당하는 값들을 or 연산 하여 두 값의 비트 자리수가 하나라도 1 이라면 1 을 반환한다.
예를 들어 100 과 010 의 | 연산의 결과값은 110 이다.
& 연산자는 각 바티 자리수에 해당하는 값들을 AND 연산하여 두 값의 비트 자리 수 모두가 1 이여야만 1 을 반환한다.
예를 들어 110 과 010 의 & 연산의 결과값은 010 이다.
비트 연산자가 해당 풀이에 어떤식으로 사용됐을까?
방문 도시 표현
N 개의 도시가 있을 때 i 번째의 방문 유무를 비트로 표현해보자
1번째 도시를 방문했다면 000...01 , 2번째 도시를 방문했다면 000...10 으로 표현된다.
이렇게 i 번째 도시의 방문 유무는 1 << i 처럼 표현 할 수 있다. 각 i 번째 자리의 비트가 1이면 되기 때문이다.
방문 도시 추가
그럼 1번째 도시를 방문한 경로 000...001 에서 2번째 도시를 추가로 방문했다면 방문 비트는 어떻게 표현 할 수 있을까?
바로 OR 연산자를 이용해 표현 할 수 있다.
000..01 | 000..10 은 000...011 이기 때문이다.
방문 유무 확인
그럼 어떤 방문 비트에서 i 번째 도시를 방문했는지 확인하는 방법은 무엇이 있을까?
그건 AND 연산자를 이용하는 것이다.
방문 비트 00...011 에서 00...100 의 방문 유무에 AND 연산자를 이용하면 3 번째 비트의 자리수가 0,1 이기 때문에 0이 반환되고 모든 비트는 000...00 이 된다.
만약 방문 비트에서 i 번째 도시가 방문 되었다면 000..1.. 이 될 것이다.
계산된 비트에 논리 연산자를 통해 해당 비트가 truty , falsy 한지 확인하면 된다.
문제 풀이의 흐름
DP 배열 생성
우선 이전 정보를 저장할 2차원 배열 DP 를 만들어준다.
해당 DP는 다음과 같은 정보를 담는다.
DP[여태까지 방문한 도시 비트][마지막에 도착한 도시 인덱스] = 해당 경로 비용의 최소값
2가지 의문이 든다.
- 여태까지 방문한 도시 비트는 어떻게 표현 할까?
위 비트 연산 파트에서 말햇듯 N 개의 도시가 있다면 N 개의 도시의 방문 경로는 000...01 부터 111...11 까지의 2 ** N 개의 비트의 조합으로 표현 할 수 있다.
- 마지막에 도착한 도시 별로 값을 왜 저장할까?
여러 방문 경로에서 마지막에 도착한 도시별로 값을 저장하는 이유는 두 가지다.
1,2 번째 도시를 순회한 도시 비트 00..011 에서 순회 가능한 다음 도시의 인덱스는 1,2 를 제외한 도시들이며 10....011 부터 00...111 이다.
현재 방문 비트로부터 다음 생성 가능한 방문 비트의 비용은 DP[생성 가능한 다음 방문 비트][도달 가능한 다음 도시 인덱스] + W[현재 도시][다음 도시] 로 구해질 수 있다.
순회의 흐름
- 방문 가능한 모든 비트를 차례대로 순회한다.
우선 방문 가능한 모든 비트를 차례대로 순회한다. 00...00 부터 11...111 까지 모두 순회한다.
모든 순회가 완료되면 모든 경로를 탐색한 것과 같다.
- 방문비트에서 현재 도달해있는 도시에서 다음 방문 비트까지의 비용을 계산한다.
이후 두, 세번째의 반복문을 통해 다음 방문 비트때의 비용을 계산한다.
이 때 두 가지 조건이 있다.
- 현재 도달해있는 도시는 방문 비트에서 존재해야한다.
이건 당연한 일이다. 00...011 방문비트에서 3번째 도시로부터 4번째 도시의 값을 계산 할 수는 없다.
- 다음에 들어가고자 하는 다음 도시는 현재 방문 비트에 없어야 한다.
이미 방문한 경로를 다시 순호하는 것은 불가능하기 때문이다.
- 현재 도시로부터 다음 도시까지 가는 경로가 존재해야 한다.
이건 당연하다. 두 도시가 연결되어있지 않다면 그 경로는 유효하지 않은 경로이다.
- 다음 방문 도시 비트에 해당하는 최소 비용을 업데이트 한다.
// 현재 탐색 경로에 netxCity를 추가한 visited 상태
const nextVisitedMask = visitedMask | (1 << nextCity);
const nextVisitedCost =
dp[visitedMask][currentCity] + W[currentCity][nextCity];
// 다음 도시를 방문하는 경우의 비용을 업데이트
dp[nextVisitedMask][nextCity] = Math.min(
dp[nextVisitedMask][nextCity],
nextVisitedCost
);이후 현재 방문 비트에서 OR 연산자를 이용해 다음 도시를 방문한 비트를 생성하고 다음 도시 방문 비트의 비용을 계산해준다.
- 마지막 도착지로부터 맨 첫 출발지로 돌아오는 값을 추가하여 최소값 계산
순회이기 때문에 마지막 지점으로부터 다시 출발지로 돌아오는 값을 계산해주면 된다.
[
[ Infinity, Infinity, Infinity, Infinity ], // 0000
[ 0, Infinity, Infinity, Infinity ], // 0001
[ Infinity, Infinity, Infinity, Infinity ], // 0010
[ Infinity, 10, Infinity, Infinity ], // 0011
[ Infinity, Infinity, Infinity, Infinity ], // 0100
[ Infinity, Infinity, 15, Infinity ], // 0101
[ Infinity, Infinity, Infinity, Infinity ], // 0110
[ Infinity, 28, 19, Infinity ], // 0111
[ Infinity, Infinity, Infinity, Infinity ], // 1000
[ Infinity, Infinity, Infinity, 20 ], // 1001
[ Infinity, Infinity, Infinity, Infinity ], // 1010
[ Infinity, 28, Infinity, 20 ], // 1011
[ Infinity, Infinity, Infinity, Infinity ], // 1100
[ Infinity, Infinity, 29, 27 ], // 1101
[ Infinity, Infinity, Infinity, Infinity ], // 1110
[ Infinity, 35, 29, 31 ] // 1111
]각 DP 배열을 살펴보자
불가능한 경로 (0번째 도시부터 시작하지 않은) 에는 값이 채워지지 않았다.
0011 을 살펴보면 0,1 번째 도시를 도달한 경우에 해당하는데 이미 출발점이 0번째 도시로 고정되어 있기 때문에 가능한 도시인 1번째 도시의 값만 계산된다.
1101 의 경우를 생각하면 이도 출발점인 0 번째 도시를 제외한 3,4 번째 도시를 마지막에 도달했을 때의 최소 비용이 담겨져있는 모습을 볼 수 있다.
오마이갓 어떻게 사람들은 이런 생각을 했을까
회고
거의 내 생각으로 풀지 못하고 대부분 남의 풀이를 보고 풀었다. 심지어 정답을 보고도 이해하는데 거진 하루 이상 걸렸다.
그럼에도 불구하고 너무 재밌었다. 어쩜 이런 똑똑이 같은 생각들을 했을까
이 게시글을 포스트 한 후 다시 혼자서 구현해봐야겠다.