[BOJ] 2098번 : 외판원 순회(C++)[Gold I]

김준형·2021년 4월 13일
1

백준

목록 보기
4/13
post-thumbnail

문제 풀러가기

Problem

Solution

  • 완전 탐색으로 이 문제를 해결하려면 O(N!)의 시간이 걸려 time limit이 발생
    But 완전 탐색시 겹치는 경우의 수가 다수 발생
  • 2차원 배열 cache[start][state]를 이용한 Memoization 구현시 시간 복잡도는 O(N2 x 2N)

    start : 출발하려는 도시의 번호,
    state : 현재 이동한 도시들을 나타낸 길이가 N인 String 배열 ex) "110"

  • N≤16 이므로 BitMask + Memoization 기법 이용시 시간 복잡도는 O(N x 2N)

    cache[start][state] 배열을 이용하지만 state변수가 int형 정수 ex) 6 = 1102

  • DFS(int start, int state)의 함수를 사용하여 경우의 수를 계산.
    초기에 DFS(0, 1)만 호출하여도 답을 구할 수 있다.

    N이 4일때 W[0][1] + W[1][2] + W[2][3] + W[3][0] = W[1][2] + W[2][3] + W[3][0] + W[0][1] 이므로

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <cstring>
#include <map>

#define MAX 2000000000 
using namespace std;

int N;
vector<vector<int>> adj(16);
int cache[16][1<<16];

bool bitCheck(int state, int i){ // state의 i번째 bit가 1이면 true, 0이면 false를 반환
	return (state & 1<<i) ? true : false;
}

int DFS(int start, int state){
	if(state == (1<<N)-1) return adj[start][0];
	if(cache[start][state] != MAX) return cache[start][state]; // cache[start][state]의 값이 존재한다면
	
	for(int i=0; i<N; i++){
		if(bitCheck(state, i)) continue; // state의 i번째 bit가 1이면 continue
		if(adj[start][i] == 0) continue; // 도시 i에서 도시 j로 갈 수 없으면 continue
		
		int ret = DFS(i, state | 1<<i);
		if(ret == 0) continue;
		cache[start][state] = min(cache[start][state], ret + adj[start][i]);
	}
	return cache[start][state];
}

int main(){
	scanf("%d", &N);
	
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++){
			int weight;
			scanf("%d", &weight);
			adj[i].push_back(weight);
		}
	
	fill(&cache[0][0], &cache[N-1][1<<N], MAX); // cache의 모든 값을 MAX로 채운다
	int first = 1; // 초기 state의 값은 1
	int mins = DFS(0, first);
	
	printf("%d \n", mins);
}

Result

  • memoization을 활용할 수 없는 코드를 짜서 time limit이 발생하였다.
    for(int i=0; i<N; i++)
    	cache[i][state|1<<i] = min(cache[i][state|1<<i], cache[start][state] + adj[start][i]);
profile
코딩하는 군인입니다.

0개의 댓글