글 읽기 - 반례가 있는지 잘 모르겠습니다

realeyes923 6년 전 0

3
0 86 0
69 0 83
45 97 0

답) 214

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

답)35

16
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

답) 16

위와 같은 테스트 케이스에서는 정상적으로 답이 나오는 것을 확인했습니다.

완전 탐색으로 구현했습니다.
몇시간동안 봤지만 어디서 잘못된건지 잘 모르겠습니다ㅠ

혹시 다른 반례가 있다면 알려주신다면 감사하겠습니다ㅠ

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int N;
int dist[17][17];
int cache[17];

bool visited[17] = { false };

int shortestPath(vector<int> &path, int currentLength)
{
    //마지막 도시와 첫번째 도시가 연결되어 있을 경우는 정상적으로 값 리턴
	if (path.size() == N && dist[path.back()][path[0]] != 0)
		return currentLength + dist[path.back()][path[0]];
    
    //마지막 도시가 첫번째 도시와 연결되어 있지 않음
	else if (path.size() == N && dist[path.back()][path[0]] == 0)
		return 987654321;

	if (cache[path.back()] != 0)
		return cache[path.back()];


	int here = path.back();
	int ret = 987654321;		//리턴할 값

	int cand;		//후보 값. 나중에 ret와 비교하게 된다.

					//여기서부터 탐색 시작. 어차피 시작점은 0이다. 1부터 끝까지 0도시와의 최소거리를 측정한다.
	for (int next = 1; next < N; next++)
	{
		if (visited[next])
			continue;

		path.push_back(next);
		visited[next] = true;

		//거리가 0이라는 것은 같은 도시, 혹은 갈수 없다는 뜻이기 때문에 예외처리한다.
		if (dist[here][next] != 0)
		{
			cand = shortestPath(path, currentLength + dist[here][next]);
			ret = min(cand, ret);
		}

		visited[next] = false;
		path.pop_back();
	}
	return cache[here] = ret;
}

int main(void)
{
	vector<int> path;

	cin >> N;

	//각 도시간의 거리를 입력받는다.
	for (int row = 0; row < N; row++)
	{
		for (int col = 0; col < N; col++)
			cin >> dist[row][col];
	}

	//사이클이 생성되기만 하면 된다. 즉, 0에서 출발해도 무방하다.
	path.push_back(0);
	visited[0] = true;

	cout << shortestPath(path, 0) << endl;
	return 0;
}

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

문제

문제

출처

ICPC

반례가 있는지 잘 모르겠습니다

realeyes923 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말