글 읽기 - 다이나믹 vs BFS 왜 다른 답이 나올까요

hazxz 7년 전 2

처음에는 다이나믹으로 풀려고 했습니다 ( DFS)

하지만 틀린 경우가 나와 밑에 문제 분류를 보니 BFS라서 BFS로 제출하니 맞았습니다가 뜨네요

DP[x][y][cnt] = x,y위치에서 k가 cnt만큼 남았을때 최소의 움직임 로 정의했습니다.

이런 방식이 DFS로 탐색을 하게 될텐데

누군가가 "먼저" 도착하게 되는 경우 그곳의 값이 최적이 아니게 되는 경우가 발생하는게 DFS인거 같은데

DP 정의를 저런식으로 해두면 각각의 위치에서 최적해를 가지게 되지 않나요?

어떤 차이가 있는지 궁금합니다.

int k, w, h;
int arr[202][202];
int DP[202][202][32];
int dx[13] = { 0,0,1,-1,-2,-1,1,2,2,1,-2,-1 };
int dy[13] = { 1,-1,0,0,-1,-2,-2,-1,1,2,1,2 };


int DFS(int x, int y, int cnt) {
	if (x < 0 || x >= h || y < 0 || y >= w) return INF;
	if (arr[x][y] == 1) return INF;
	if (x == h - 1 && y == w - 1) return 0;

	int& ret = DP[x][y][cnt];
	if (ret != -1) return ret;

	ret = INF;
	for (int i = 0; i < 4; i++) {
		ret = min(ret, 1 + DFS(x + dx[i], y + dy[i], cnt));
	}
	if (cnt > 0) {
		for (int i = 4; i < 12; i++) {
			ret = min(ret, 1 + DFS(x + dx[i], y + dy[i], cnt - 1));
		}
	}
	return ret;
}
struct Point {
	int x, y, cnt, cost;
	Point(int a, int b, int c, int d) : x(a), y(b), cnt(c), cost(d) {}
	Point() { cost = 0; }
};

int BFS(int x, int y, int cnt) {
	queue<Point> q;
	q.push(Point(x, y, cnt, 0));

	int ans = INF;

	while (!q.empty()) {
		Point cur = q.front();
		q.pop();

		if (cur.x == h - 1 && cur.y == w - 1) {
			ans = min(ans, cur.cost);
		}

		if (DP[cur.x][cur.y][cur.cnt] != -1) continue;
		DP[cur.x][cur.y][cur.cnt] = 0;

		int nextX, nextY, nextCnt;
		for (int i = 0; i < 4; i++) {
			nextX = cur.x + dx[i];
			nextY = cur.y + dy[i];
			nextCnt = cur.cnt;
			if (nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
			if (arr[nextX][nextY] == 1) continue;
			q.push(Point(nextX, nextY, nextCnt, cur.cost + 1));
		}
		if (cur.cnt <= 0) continue;
		for (int i = 4; i < 12; i++) {
			nextX = cur.x + dx[i];
			nextY = cur.y + dy[i];
			nextCnt = cur.cnt - 1;
			if (nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
			if (arr[nextX][nextY] == 1) continue;
			q.push(Point(nextX, nextY, nextCnt, cur.cost + 1));
		}
	}
	return ans;
}

int main() {

	scanf("%d", &k);
	scanf("%d %d", &w, &h);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	memset(DP, -1, sizeof(DP));
	int ans = BFS(0, 0, k);
	ans == INF ? printf("-1\n") : printf("%d\n", ans);

	return 0;
}

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

문제

문제

출처

ICPC

다이나믹 vs BFS 왜 다른 답이 나올까요

hazxz 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말