글 읽기 - 아.....고수님들 진심 헬프..... 제발..

zagame 7년 전 0

다시 출발점으로 돌아오는 줄 모르고

예를 들어 a,b,c,d 4개 점 있으면

a->b->c->d 요렇게 한번씩만 방문해서 최단거리 구하는 걸로 풀었는데...

알고보니 다시 출발점으로 이렇게 a->b->c->d->a 로 돌아 올때의 최소값이더라구요...?

아.... 이 코드에서 저대로 동작하게 수정해볼라는데 잘 안됌 아 ㅠㅠㅠㅠㅠㅠ

이코드 못 살리려나요....? 출발점 되돌아오는 생각 안하고 짠거라서 ㅠㅠㅠㅠㅠ

/*
* tsp.c
*
*  Created on: 2016. 5. 2.
*      Author: Administrator
*/


#include <stdio.h>


int N;
int W[16][16]; // i->j weight, 0 = path X
int memory[16][1<<16]; // for memoization

int TSP(int from, int toFlag);
int bitCount(int n);
int getIndex(int n);
int MIN(int a, int b);

int main(void)
{
	int m, i, j, allFlag, v;

	//1. input
	scanf("%d", &N);
	for (i = 0; i<N; i++)
		for (j = 0; j<N; j++)
			scanf("%d", &W[i][j]);

	m = 999999;
	allFlag = (1 << N) - 1;

	//2. TSP
	for (i = 0; i<N; i++)
	{
		v = TSP(i, allFlag & ~(1<< i)); // i 제외한 나머지 그룹
		m = MIN(m, v);
	}

	printf("%d", m);

	return 0;
}
int TSP(int from, int toFlag)
{
	int i, v, to, memo;

	memo = memory[from][toFlag];
	if (memo != 0)
	{
		return memo;
	}
	if (bitCount(toFlag) == 1) // 남은 도시가 1개 라면
	{
		to = getIndex(toFlag);
		return W[from][to];
	}

	memo = 999999;
	for (i = 0; i<N; i++)
	{
		if (!(toFlag & (1 << i))) continue; // toFlag에 포함되지 않은 도시 skip

		v = W[from][i] + TSP(i, (toFlag & ~(1<<i)) );
		memo = MIN(memo, v);
	}

	memory[from][toFlag] = memo;
	return memo;
}
int bitCount(int n)
{
	int i = 1, cnt = 0;
	while (1)
	{
		if (i > n)
			break;
		if (n & i)
			cnt++;
		i = i << 1;
	}
	return cnt;
}
int getIndex(int n)
{
	int i = 1, idx = 0;
	while(1)
	{
		if (n == i)
			break;
		else
		{
			i = i << 1;
			idx++;
		}
	}
	return idx;
}
int MIN(int a, int b)
{
	if (a < b) return a;
	else return b;
}

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

문제

문제

출처

ICPC

아.....고수님들 진심 헬프..... 제발..

zagame 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말