글 읽기 - DP의 아이디어가 필요합니다.

nuricook 7년 전 0

안녕하세요,

이 문제는, BFS를 사용해서 풀었습니다.
벽이란 존재를 map에서 가중치를 1로 가지는 node로, 빈 방은 가중치를 0으로 가지는 node로 설정하고,
solve(int x, int y);은 "(x, y) ~ (N,M) 까지의 경로 중 가중치 합이 가장 적은 경로를 찾고, 해당 가중치 합을 반환하라"
라는 문제로 이해했습니다.

만약 빈 방으로만 N,M까지 가지 못하고 벽을 통과해야 했다면, 벽1개당 가중치 1씩 증가했을텐데요,
이 결과를 바로 출력하면 반대로 벽을 몇 개 뚫어야 목적지에 도착하는가? 에 대한 문제를 풀 수 있다고 생각했습니다.

실제로 결과도 잘 나오는 것 같네요. (추측입니다만..)

문제는, cache에 따른 "메모리 초과"로 나온다는게 문제랄까요 ^^;;;

아직, 문제 형태에 따른 적절한 cache를 사용하는게 익숙하지 않은 탓인지,
cache를 잡을 때, x, y (검색 중 현재위치) 와 x, y까지 오면서 생긴 가중치의 합으로 cache를 했습니다.

2 가지 걱정이 있습니다.

- 1. 과연 현재위치까지 오는데에 가중치의 합으로 cache를 구분하는게 옳은 방법인가?

- 2. 메모리 초과를 풀기위한 다른 접근방법은 무엇인가?

입니다.

혹시, 생각을 공유해주실 수 있다면 제게 도움이 많이 될 것 같습니당. :)

#include <stdio.h>

#define MAXN 101
#define INF MAXN*MAXN
int map[MAXN][MAXN];
int visited[MAXN][MAXN];
int cache[MAXN][MAXN][INF];
int N, M;

void intput()
{
	scanf("%d %d\n", &M, &N);
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			char c;
			scanf(" %c", &c);
			if (c == '1') {
				map[i][j] = 1;
			} else {
				map[i][j] = 0;
			}
			visited[i][j] = 0;
			int k;
			for (k = 0; k <= N*M; k++) {
				cache[i][j][k] = -1;
			}
		}
	}
}

int min(int a, int b)
{
	return a < b ? a : b;
}

// solve: 0,0에서 N,M까지의 경로중 비용이 가장 낮은 경로값을 반환한다.
// 값1인 막힌방을 지났다면 1*벽의수의 값으로 반환으로, 지나간 벽의 수가나오고, 안지나도 된다면 0이 나온다.
int solve(int x, int y, int curminlen)
{
	if (x == N - 1 && y == M - 1)
		return 0;
	if (x < 0 || x >= N || y < 0 || y >= M)
		return INF;
	if (visited[x][y] == 1)
		return INF;

	if (cache[x][y][curminlen] != -1) {
		return cache[x][y][curminlen];
	}

	visited[x][y] = 1;

	int minlen = INF;
	minlen = min(solve(x + 1, y, minlen) + map[x][y], minlen);
	minlen = min(solve(x - 1, y, minlen) + map[x][y], minlen);
	minlen = min(solve(x, y + 1, minlen) + map[x][y], minlen);
	minlen = min(solve(x, y - 1, minlen) + map[x][y], minlen);

	visited[x][y] = 0;
	return cache[x][y][curminlen] = minlen;
}

int main()
{
	setbuf(stdout, NULL);

	intput();
	printf("%d\n", solve(0, 0, N*M));

	return 0;
}

yukariko 7년 전 2

"벽이란 존재를 map에서 가중치를 1로 가지는 node로, 빈 방은 가중치를 0으로 가지는 node로 설정하고,solve(int x, int y);은 "(x, y) ~ (N,M) 까지의 경로 중 가중치 합이 가장 적은 경로를 찾고, 해당 가중치 합을 반환하라"라는 문제로 이해했습니다."

이것으로 보아 이 문제를 가중치가 있는 그래프문제로 생각할 수 있고, 시작점으로부터 끝점까지 가기위한 최단경로를 찾는 문제로 생각할 수 있습니다.

따라서 최단경로 알고리즘을 사용할 수 있죠.