글 읽기 - 10971번 외판원 순회2 문제 어디가 틀렷는지 모르겠어요

wb998 5년 전 0

외판원 순회2 문제에서 최단 경로를 찾아가면서 최소가 되는 값을 구햇는데 예제는 맞게 나옵니다만 왜 틀렸는지 모르겠네요 ㅠ.ㅠ 고수분들

소스 문제점좀 알려주세요

#include <iostream>

using namespace std;

int map[11][11];
bool check[11];

int n; //도시의 갯수



int Go(int start,int sum,int cnt,int fiStart) //a는 S cnt는 순회 횟수 fiStart = firstStart
{
	int min = 9999999;
	int index;
	check[start] = true;
	if (cnt == 4) {
		sum += map[start][fiStart];
		return sum;
	}
	for (int i = 0; i < n; i++) {
		if (min > map[start][i] && i != start && !check[i]) {
			min = map[start][i];
			index = i;
		}
	}
	sum += map[start][index];
	Go(index, sum,++cnt,fiStart);
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	int sum = 0; //갈 수 있는 경로의 합
	int ans = 9999999;

	for (int s = 0; s < n; s++) { //S가 4번돌아야 함
		sum = Go(s,0,1,s);
		if (ans > sum) ans = sum;

		for (int i = 0; i < n; i++) {
			check[i] = false;
		}
	}

	cout << ans;

	return 0;
}

djm03178 5년 전 0

17번째 줄에서 왜 cnt가 무조건 4일 때가 끝이라고 가정하셨나요?

wb998 5년 전 0

헉 맞네요 이런 기초적인 실수를 ㅠ.ㅠ 하지만 cnt를 도시 갯수만큼 돌게 만들어도 오답이라고 뜨네요 ㅠ.ㅠ

djm03178 5년 전 0

0은 갈 수 없는 길인데 갈 수 있는 것처럼 행동하네요.

djm03178 5년 전 3

또한, 각 정점에서 지금 당장 갈 수 있는 가장 짧은 간선을 선택하는 것이 최적이라는 보장은 없습니다.

wb998 5년 전 0

아.. 무조건 최단 거리만 찾아가면 되는 문제가 아니군요 답변 감사합니다

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

문제

문제

출처

ICPC

10971번 외판원 순회2 문제 어디가 틀렷는지 모르겠어요

wb998 5년 전 0

djm03178 5년 전 0

wb998 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 3

wb998 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말