글 읽기 - 2394번 드라이버 투어 문제 질문 드립니다.

hbh1107 7년 전 0

안녕하세요 2394번 드라이버 투어 문제를 풀던중 막혀서 몇주째 고민하다 게시판에 글올립니다.

소스 코드를 같이 올립니다 조언 주시면 감사하겠습니다.

문제 풀이 방식 : KOI 2008 공주구하기 문제와 같은 방식으로 풀었습니다.

DP[a][b] : 가는 위치가 a이고 오는 위치가 b일때 최대 방문 도시 갯수.

calc(a,b,k) <= 현재 가는 위치가 a에 있고 오는 위치가 b이며 다음 탐색할 위치가 k일때 a,b,k+1 경우, k,b,k + 1경우, a,k,k+1의 경우 중 최댓값으로 갱신했습니다.

find_path() 위 calc 함수로 최댓값을 역추적 하기위해서 현재 위치가 a,b일때 다음 이동 지점을 path에 저장했습니다.

조언 주시면 정말 감사하겠습니다.

#include <stdio.h>

#define INF 0x7fffff
#define MAXN 260

int N;
int idx1, idx2;
int path1[MAXN];
int path2[MAXN];
int map[MAXN][MAXN];
int memo[MAXN][MAXN];

int max(int a, int b) { if (a > b) return a; else return b; }

int calc(int a, int b, int k)
{
	int ret;

	if (k == N) {
		if (map[a][N] && map[b][N])
			return memo[a][b] = 1;
		else
			return -INF;
	}

	if (memo[a][b] != -1)
		return memo[a][b];

	memo[a][b] = max(calc(a, b, k + 1), memo[a][b]);
	if (map[a][k]) {
		ret = calc(k, b, k + 1) + 1;
		memo[a][b] = max(ret, memo[a][b]);
	}

	if (map[b][k]) {
		ret = calc(a, k, k + 1) + 1;
		memo[a][b] = max(ret, memo[a][b]);
	}

	return memo[a][b];
}

void init()
{
	int i, j;
	idx1 = idx2 = 0;
	for (i = 0; i <= N; i++)
		for (j = 0; j <= N; j++)
			memo[i][j] = -1, map[i][j] = 0;
	path1[0] = 1; path2[0] = 1; path1[++idx1] = N;
}


void find_path(int a, int b)
{
	int i, mx_a, mx_b, nexta, nextb;

	if (a == N && b == N)
		return;

	mx_a = -INF; mx_b = -INF;
	for (i = a + 1; i <= N; i++) {
		if (map[a][i] && i != b && memo[i][b] > mx_a) {
			mx_a = memo[i][b];
			nexta = i;
		}
	}

	for (i = b + 1; i <= N; i++) {
		if (map[b][i] && i != a && memo[a][i] > mx_b) {
			mx_b = memo[a][i];
			nextb = i;
		}
	}

	if (mx_a > 0 || mx_b > 0) {
		if (mx_a > mx_b) {
			path1[++idx1] = nexta;
			find_path(nexta, b);
		}
		else {
			path2[++idx2] = nextb;
			find_path(a, nextb);
		}
	}
}

void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }

void sort()
{
	int i, j;
	for (i = 0; i < idx1; i++)
		for (j = i + 1; j <= idx1; j++) {
			if (path1[i] > path1[j]) swap(&path1[i], &path1[j]);
		}
	for (i = 0; i < idx2; i++)
		for (j = i + 1; j <= idx2; j++) {
			if (path2[i] < path2[j]) swap(&path2[i], &path2[j]);
		}
}




int main()
{
	int i, j, ret, p, q, mx, tmp_idx;

	scanf("%d", &N);
	init();
	do {
		scanf(" %d %d", &p, &q);
		map[p][q] = 1;
		map[q][p] = 1;
	} while (p && q);

	ret = calc(1, 1, 2);

	if (ret <= 0) {
		printf("0\n");
	}
	else if (ret == 1) {
		printf("2\n1 %d 1\n", N);
	}
	else {
		find_path(1, 1);
		printf("%d\n", ret + 1);
		sort();
		for (i = 0; i <= idx1; i++)
			printf("%d ", path1[i]);
		for (i = 0; i <= idx2; i++)
			printf("%d ", path2[i]);
		printf("\n");
	}

	return 0;
}

zlzmsrhak 7년 전 0

메모이제이션 이런식으로 쓸 거면 쓰지 마세요.

1. 21번째 줄에서 memo[a][b]에 값이 있으면 원래 있던 값이 지워집니다.

2. memo 배열의 초기값이 너무 큽니다.

계산 과정에서 언젠가 -1이 리턴되고, 여기에 1이 더해지면서 0 이상의 값인 valid한 값으로 바뀝니다.

반례로, N = 256, N <= 255의 완전그래프를 입력으로 주면 이상한 경로를 출력합니다.

3. 역추적이 잘못됐습니다.

(a, b)가 (2, 4) -> (2, 5) -> (4, 5) 순으로 4가 겹치게 역추적이 될 수 있습니다.

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

문제

문제

출처

ICPC

2394번 드라이버 투어 문제 질문 드립니다.

hbh1107 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말