글 읽기 - 틀린 부분을 잘 모르겠습니다.

lvhi0607 2년 전 0

안녕하세요. 외판원 순회 문제를 풀다가 도저히 잘못된 부분을 찾기 어려워 고수분들의 도움을 받고자 질문글을 올립니다.

우선 문제를 보고

1. 주어진 경로(가중치)를 이차원 배열에 저장한 후

2. Floyd-Warshall 알고리즘으로 각 정점에서 다른 모든 정점으로 가는 최소 가중치를 갱신한 후

3. 임의의 한 정점(코드 상에선 1번 정점)에서 출발해 DFS 형태로 모든 정점을 1번만 방문 후 다시 출발지로 돌아오는 경우의 최소 비용을 구하였습니다.

DFS의 시간복잡도 개선을 위해 메모이제이션 (배열 D)을 이용했습니다. 그런데 이 방식대로 작성한 코드를 제출하면 틀렸다고 나오네요..

예시 입력이 1개뿐이라, 반례를 찾기도 어렵습니다.. 어느 부분에 문제가 있을까요? ㅠ

#define _CRT_SECURE_NO_WARNINGS
#define MAXN 17
#define INF 0x6FFFFFFF

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, W[MAXN][MAXN];
int D[MAXN][(1 << 16)];
int find(int x, const int dest, int check, int cost);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	//freopen("input.txt", "r", stdin);
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> W[i][j];
		}
	}

	// Floyd-Warshall
	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (i == j)
				{
					continue;
				}
				if ((W[i][k] && W[k][j]) && W[i][j] > W[i][k] + W[k][j])
				{
					W[i][j] = W[i][k] + W[k][j];
				}
			}
		}
	}
	// 1번 정점에서 출발하며, 1번 정점으로 되돌아와야 하고 1번에서 시작하므로 방문 비트의 오른쪽에서 첫 번째(2^0) 비트 set, 출발 비용은 없으므로 0으로 호출
	int answer = find(1, 1, 1, 0);
	cout << answer << "\n";

	return 0;
}

int find(int x, const int dest, int check, int cost)
{
	// 모든 정점을 방문했다면
	if (check == (1 << N) - 1)
	{
		// 출발 정점으로 돌아갈 수 없는 경우(인접하지 않은 경우)
		if (!W[x][dest])
		{
			return INF;
		}
		// 돌아갈 수 있는 경우
		else
		{
			return cost + W[x][dest];
		}
	}
	// 이미 현재 방문 상태에서의 탐색 결과가 메모되어 있다면 해당 값을 리턴
	if (D[x][check])
	{
		return D[x][check];
	}
	int answer = INF;
	for (int i = 1; i <= N; i++)
	{
		if (i == x)
		{
			continue;
		}
		// 방문하지 않은 인접한 모든 정점을 방문해 본 후 그 중 최소 비용을 선정
		if (W[x][i] && !(check & (1 << (i - 1))))
		{
			auto nextCheck = check | (1 << (i - 1));
			int result = find(i, dest, nextCheck, cost + W[x][i]);
			answer = answer > result ? result : answer;
		}
	}
	// 현재 정점에서 모든 경로 탐색 후 출발지로 돌아가는 최소 비용을 메모 후 리턴
	D[x][check] = answer;

	return D[x][check];
}

lcr7324 2년 전 0

floyd-warshall을 돌린 부분이 문제가 아닐까요? 예컨대 정점 A에서 B로 바로 가는 경로의 비용이 10인데, C를 거쳐서 가면 5로 줄어들고 이게 A와 B 사이의 최단거리라 합시다.

그러면 이제 DFS에서 A -> B -> C 같은 경로를 답으로 계산하게 된다면 이는 사실 C를 중복으로 방문한 것이 됩니다.

floyd-warshall 부분을 아예 제외하고 실행하면 어떨까 싶습니다.

lvhi0607 2년 전 0

@lcr7324 답변 감사합니다. 생각해보니 말씀하신대로 특정 경유지를 거치는 최단 경로를 찾으면 안되는 거였네요... 다만 해당 코드를 제거한 후 돌려도 6%에서 틀렸습니다 가 나옵니다 ㅠㅠ 플로이드와샬 외에도 다른 잘못된 부분이 있는 것 같습니다.

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

문제

문제

출처

ICPC

틀린 부분을 잘 모르겠습니다.

lvhi0607 2년 전 0

lcr7324 2년 전 0

lvhi0607 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말