글 읽기 - TSP(1,1) 로 시작하면 틀리나요?

colorxxx 5년 전 0

1,1 부터 시작하는게 직관적이어서 저렇게 했는데 답도 틀리게나오고,,,런타임에러도 뜨네요 ㅠㅠ

TSP2 가 0,1로 시작하는 코드인데 입력바꿔주고 하면 맞는데

TSP 함수 1,1부터하면 똑같이 짯다고 생각했는데 런타임에러 + 답까지 틀리네요

코드중 어디가 문제인걸까요 ..

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include<string.h>
using namespace std;
#define IMP 1000000001

int N;
int W[17][17];
int d[17][65537];
int start = 0;

int TSP(int idx, int visited) {
	if (visited == (1 << N) - 1) {
		return W[idx][1] ? W[idx][1] : IMP; //돌아가는 경로 없으면 IMP 리턴.. min에서 걸러진다.
	}

	int &ret = d[idx][visited]; //visited 라는 다차원배열 만들기! 1->N까지경로 모두를 포함하는 배열
	if (ret != -1) return ret; //memoization. 
	ret = IMP; //이 두줄이핵심! 없으면 시간초과.. 먼저 -1로 초기화시킨 상태에서 dp배열 검사하고 값이 있으면 리턴
			   //값이 없으면 MAX로 초기화하고

	for (int i = 1; i <= N; i++) {
		if (W[idx][i] != 0) { //만약 idx->i로 가는 경로가 존재할때
			if (!(visited &(1 << i))) { // i 번 정점이 방문되지 않은 경우
				ret = min(ret, TSP(i, (visited | 1 << i)) + W[idx][i]);
			}
		}
	}
	return ret;


}


int TSP2(int idx, int visited) {
	if (visited == (1 << N) - 1) {
		return W[idx][0] ? W[idx][0] : IMP; //돌아가는 경로 없으면 IMP 리턴.. min에서 걸러진다.
	}

	int &ret = d[idx][visited]; //visited 라는 다차원배열 만들기! 1->N까지경로 모두를 포함하는 배열
	if (ret != -1) return ret; //memoization. 
	ret = IMP; //이 두줄이핵심! 없으면 시간초과.. 먼저 -1로 초기화시킨 상태에서 dp배열 검사하고 값이 있으면 리턴
			   //값이 없으면 MAX로 초기화하고

	for (int i = 0; i < N; i++) {
		if (W[idx][i] != 0) { //만약 idx->i로 가는 경로가 존재할때
			if (!(visited &(1 << i))) { // i 번 정점이 방문되지 않은 경우
				ret = min(ret, TSP2(i, (visited | 1 << i)) + W[idx][i]);
			}
		}
	}
	return ret;

}


int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> W[i][j];
		}
	}
	memset(d, -1, sizeof(d));


	cout << TSP(1, 1); //싸이클 경로를 찾는것이기 때문에 출발지점을 어디로 선정하든 상관없다.


}

yoonsang9114 5년 전 1

1,1은 전혀 직관적이지 않습니다.

일단 질문자님의 TSP함수에서는 비트를 최대 N만큼, 즉 16까지 밀기때문에 2^16으로 선언된 배열을 초과해서 런타임 에러가 나는겁니다.

그리고 0,1인 이유는 0번마을을 방문할때 000000000001, 1번 비트를 켜기때문에 0,1이고 1로 시작하고 싶다면 1,2로 시작하는게 맞는것같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include<string.h>
using namespace std;
#define IMP 1000000001

int N;
int W[17][17];
int d[17][65537];// 65537= 2^16질문자님 런타임 에러의 이유, tsp2함수에서는 N-1번까지 비트를 밀기때문에 에러가 나지 않음
int start = 0;

int TSP(int idx, int visited) {
	if (visited == (1 << N) - 1) {
		return W[idx][1] ? W[idx][1] : IMP; 
	}

	int &ret = d[idx][visited]; 
	if (ret != -1) return ret; 
	ret = IMP; 
	for (int i = 1; i <= N; i++) {//비트를 최대 N번 미는 코드
		if (W[idx][i] != 0) { 
			if (!(visited &(1 << i))) { 
				ret = min(ret, TSP(i, (visited | 1 << i)) + W[idx][i]);
			}
		}
	}
	return ret;
}

//1번마을부터 시작할 때 ac받는 코드
int N;
int W[17][17];
int d[17][1<<17];
int start = 0;

int TSP(int idx, int visited) {
	if (visited == (1 << (N+1)) - 2) {
		return W[idx][1] ? W[idx][1] : IMP; 
	}

	int &ret = d[idx][visited]; 
	if (ret != -1) return ret; 
	ret = IMP; 

	for (int i = 1; i <= N; i++) {
		if (W[idx][i] != 0) {
			if (!(visited &(1 << i))) { 
				ret = min(ret, TSP(i, (visited | 1 << i)) + W[idx][i]);
			}
		}
	}
	return ret;


}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> W[i][j];
		}
	}
	memset(d, -1, sizeof(d));


	cout << TSP(1, 2);


}

yoonsang9114 5년 전 1

16개 비트를 사용하면서 TSP(1,1)로 시작하는 AC코드입니다.

비트 미는횟수를 한번씩 빼주면 동작합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include<string.h>
using namespace std;
#define IMP 1000000001

int N;
int W[17][17];
int d[17][1<<16];

int TSP(int idx, int visited) {
	if (visited == (1 << N) - 1) {
		return W[idx][1] ? W[idx][1] : IMP; 
	}

	int &ret = d[idx][visited]; 
	if (ret != -1) return ret; 
	ret = IMP; 

	for (int i = 1; i <= N; i++) {
		if (W[idx][i] != 0) {
			if (!(visited &(1 << (i-1)))) { 
				ret = min(ret, TSP(i, (visited | 1 << (i-1))) + W[idx][i]);
			}
		}
	}
	return ret;


}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> W[i][j];
		}
	}
	memset(d, -1, sizeof(d));


	cout << TSP(1, 1);


}

colorxxx 5년 전 0

아하... 비트에 그런 의미가 있었군요! 정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

TSP(1,1) 로 시작하면 틀리나요?

colorxxx 5년 전 0

yoonsang9114 5년 전 1

yoonsang9114 5년 전 1

colorxxx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말