글 읽기 - dp로는 왜 해결할 수 없는지 궁금합니다

hssk1528 5년 전 0

문제가 bfs를 활용해야한다는 건 확인했습니다만 처음 문제를 읽고 생각난 알고리즘이 dp라서 dp로 구현을 해보았습니다.

그리고 오답을 받아서 질문글을 찾아보던 중 저랑 거의 비슷하게 구현하신 분 글을 봤는데 답변에 dp에는 visited를 적용하면 안된다고 하시더라구요

저는 visited를 무한루프 도는 것을 방지하기 위해서 사용하였는데 왜 안되는지도 궁금합니다ㅜㅜ

그 질문글에 있던 반례도 맞게 나오는데 말이죠...

어떤 부분에서 틀렸는지, dp로는 시간문제때문에 해결할 수 없는것인지 궁금합니다

#include <iostream>
#include <algorithm>

using namespace std;

int k;  // 말처럼 이동할 수 있는 최대 횟수
int w, h;  // 가로, 세로 길이
int map[200][200];  // 격자판의 상태
int cache[200][200][31];
int visited[200][200];

const int INF = 987654321;
const int hx[8] = { -1,-2,-2,-1,1,2,2,1 };  // 말처럼 이동
const int hy[8] = { -2,-1,1,2,-2,-1,1,2 };
const int mx[4] = { -1,1,0,0 };  // 상하좌우 이동
const int my[4] = { 0,0,-1,1 };

int traveling(int x, int y, int horse) {
	// base case : 현재 위치가 장애물이거나 이미 방문한 곳이라면 INF 리턴
	if (map[x][y] == 1 || visited[x][y] == 1) return INF;

	// base case : 현재 위치가 마지막 지점이라면 종료
	if (x == h - 1 && y == w - 1) return 0;

	// 메모이제이션
	int& ret = cache[x][y][horse];
	if (ret != -1) return ret;

	visited[x][y] = 1;

	// 말처럼 이동할 수 있는 횟수가 남았다면 말처럼 이동
	int cand1 = INF;
	if (horse > 0) {
		for (int dir = 0; dir < 8; dir++) {
			int nx = x + hx[dir];
			int ny = y + hy[dir];

			// 범위 확인
			if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;

			cand1 = min(cand1, traveling(nx, ny, horse - 1) + 1);
		}
	}
	
	// 인접한 칸 이동(상하좌우)
	int cand2 = INF;
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + mx[dir];
		int ny = y + my[dir];

		// 범위 확인
		if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;

		cand2 = min(cand2, traveling(nx, ny, horse) + 1);
	}

	visited[x][y] = 0;
	return ret = min(cand1, cand2);
}

int main() {
	cin >> k;
	cin >> w >> h;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}

	// 캐시 메모리 초기화
	for (int i = 0; i < 200; i++) {
		for (int j = 0; j < 200; j++) {
			for (int k = 0; k <= 30; k++) {
				cache[i][j][k] = -1;
			}
		}
	}

	int res = traveling(0, 0, k);
	if (res >= INF) cout << "-1" << endl;
	else cout << res << endl;
	return 0;
}

이 예시의 경우 맨 처음 오른쪽으로 출발해서 가면 10번이면 도착이 가능하지만, 이 코드에서는 (입력 전체 기준으로) 9행 4열에 말 이동 횟수를 1 남기고 가장 먼저 도달하는 경로는 처음에 아래 방향으로 출발한 경로입니다. 그런데 이때는 11행 5열의 0을 거쳐서 방문했기 때문에 visited 체크가 되어있어, 11행 5열로 다시 거쳐서 내려가면 3번만에 끝에 도달할 수 있음에도 불구하고 ret가 inf가 되고 맙니다.

나중에 처음에 오른쪽으로 출발한 경로를 따라서 다시 9행 4열에 말 이동 횟수를 1 남기고 도달했을 때는 ret가 -1이 아니기 때문에 그대로 inf를 반환하게 되고, 그래서 이 경로가 더 짧을 수 있음에도 불구하고 프로그램은 처음에 아래로 출발했을 때의 이동 경로인 12를 출력하게 됩니다.

traveling 함수 수행 이후 해당 칸의 dp값 (cache[6][3][1])을 출력해보세요.

hssk1528 5년 전 0

자세한 설명 정말 감사드립니다ㅠㅠ 왜 dp로는 풀 수 없는지 확실하게 이해하게 되었어요

그래서 bfs로 다시 짜고 정답받았습니다

항상 도움 많이 받네요 감사합니다!!

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

문제

문제

출처

ICPC

dp로는 왜 해결할 수 없는지 궁금합니다

hssk1528 5년 전 0

djm03178 5년 전 3

hssk1528 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말