글 읽기 - 외판원 순회 - 다른 접근 방식을 택했는데 왜 틀린지 모르겠습니다

Green55 6년 전 0

아래가 처음 제출했던 코드고, 위가 AC가 뜬

처음에 0번 정점을 방문하지 않았다고 가정하고, 모든 정점을 방문했을 때 순회를 끝내는 식으로 코드를 짰는데 왜 WA일까요

//AC

#include<bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, w[16][16], finish, dp[16][1<<16];
int path(int here, int visit){
    //----------------------------//
	if(visit == finish){
		if(!w[here][0]) return INF;
		else return w[here][0];
	}
    //----------------------------//
	int &ret = dp[here][visit];
	if(ret!=-1) return ret;
	ret = INF;
	for(int there=0; there<n; there++){
		if(!w[here][there]) continue;
		if(visit & (1<<there)) continue;
		ret = min(ret, w[here][there] + path(there, visit|(1<<there)));
	}
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", &w[i][j]);
	finish = (1<<n)-1;
	memset(dp,-1,sizeof(dp));
    //---------------------//
	printf("%d", path(0,1));
    //---------------------//
}

 
//WA
#include<bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, w[16][16], finish, dp[16][1<<16];
int path(int here, int visit){
    //--------------------------//
	if(visit == finish) return 0;
    //--------------------------//
	int &ret = dp[here][visit];
	if(ret!=-1) return ret;
	ret = INF;
	for(int there=0; there<n; there++){
		if(!w[here][there]) continue;
		if(visit & (1<<there)) continue;
		ret = min(ret, w[here][there] + path(there, visit|(1<<there)));
	}
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", &w[i][j]);
	finish = (1<<n)-1;
	memset(dp,-1,sizeof(dp));
    //---------------------//
	printf("%d", path(0,0));
    //---------------------//
}

vjerksen 6년 전 1

왜 WA 인가에 대한 저의 의견

1. 출발 지점으로 다시 돌아올 수 있다.

: 0 -> 1 -> 0 -> 2 -> 3 와 같이 다시 돌아올 수 있다고 생각합니다. 기존에 0(0001) -> 1(0011) -> 2(0111) -> 3(1111) 이 최소 비용 거리라고 가정한다면, 결국 0(0000) -> 1(0010) -> 0(0011) -> 2(0111) -> 3(1111) (차선의 경로라고 가정) 으로밖에 이동할 수 없을 것입니다.

2. 기저 조건에서 돌아오는 조건이 없다.

: 모든 지점을 방문했지만, 다시 돌아오는 길이 없다면 문제가 될 것입니다.

틀린 부분있으면 조언 부탁드립니다.

Green55 6년 전 1

뒤늦은 후기 : if문에서 here 이 시작 정점일때만 0을 리턴하고, 아닐때는 INF를 리턴하니 AC가 뜨네요. 감사합니다.

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

문제

문제

출처

ICPC

외판원 순회 - 다른 접근 방식을 택했는데 왜 틀린지 모르겠습니다

Green55 6년 전 0

vjerksen 6년 전 1

Green55 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말