글 읽기 - 0번마을 출발 -> 0번마을 도착만 처리해도 정답이 되는건가요?

esuperstar 5년 전 0

https://kswims.tistory.com/176

아래 코드는 여기서 찾아본 소스코드인데요

이 소스코드로 dp테이블을 채우면

0번마을에서 출발해서 0번마을로 돌아온 경우만 처리해주는거 아닌가요?

1번마을 출발 -> 1번마을 도착, 2번마을 출발-> 2번마을 도착 .......... 등등의 케이스도 이 코드로 처리가 되는지 궁금합니다.

#include<iostream>

using namespace std;

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

int TSP(int curr, int visited)
{ //현재 몇번 째 마을에 위치하는지, 어느 마을을 방문하고 왔는지
	int result;
	int ret = dp[curr][visited];

	if (ret != 0) //이미 구한 적 있다면
		return ret;

	if (visited == (1 << N) - 1) 
	{ //모든 마을 방문했을 때
		if (W[curr][0] != 0) 
		{ //0번 마을로 갈 수 있을 때
			return W[curr][0];
		}
		return 1000000000; //불가능 하도록 매우 큰 수를 return
	}

	ret = 1000000000;

	for (int i = 0; i<N; i++) 
	{
		if ((visited & 1 << i) || (W[curr][i] == 0)) //i번째 visited 를 확인하기 위한 bit 연산
			continue;
		
		result = TSP(i, (visited | 1 << i)) + W[curr][i];
		
		if (result < ret)
			ret = result;
	}
	dp[curr][visited] = ret;
	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]);

	printf("%d\n", TSP(0, 1));

	return 0;
}

djm03178 5년 전 1

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

0번마을 출발 -> 0번마을 도착만 처리해도 정답이 되는건가요?

esuperstar 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말