sourish92   2년 전

안녕하세요.

문제 분류가 BFS로 되어있지만, DP 접근으로 풀 수 있을 것같아서 메모이제이션을 사용한 DFS로 문제를 풀었습니다.

미로탐색 문제가 재채점되면서 틀렸습니다가 뜨는 것 같은데, 이유를 모르겠어서 질문을 남기게 되었습니다.

게시판들에 있는 반례들을 돌렸을 때 정답이 잘 출력되는데, 어떤 문제가 있을까요?

이전 질문에서 2차원 DP, 즉 현재 위치만을 이용해서는 최적해를 구할 수 없다는 답변이 달렸는데

이 부분이 잘 이해가 안되서 질문드립니다.

캐시배열에 저장되어 있는 값은 현재 위치에서의 최적해를 담고 있기 때문에, 부분 최적해를 만족하고

이 부분 최적해를 이용해서 최적해를 구할 수 있지 않나요..?

혹시 반례를 알려주신다면 감사하겠습니다.

아래는 제 코드입니다!

djm03178   2년 전

다른 질문글에서 탐색 순서만 바꿨더니 잘 되는 건 그 순서대로 갔을 때 우연히 정답이 되는 쪽으로 탐색이 되었을 뿐입니다.

rdd6584   2년 전

맨 처음 도착했던 그래프의 방문 상태와 두번째로 방문했을 때 방문 상태가 다를 수 있기 때문에 메모이제이션을 적용할 수 없습니다.

Green55   2년 전

부분문제관의 의존성을 따져봤을 때, 사이클이 존재하는 경우에는 dp를 이용 할 수 없습니다.

이 문제는 예를 들면 (0,0)에서의 최단거리를 구하기 위해 (0,1)에서의 최단거리를 사용하고,

(0,1)에서의 최단거리를 구하기 위해서 (0,0)의 최단거리를 필요로 합니다.

코드 흐름을 따라가보면서 예시를 들어보겠습니다.

proc(0,0)의 부분문제를 반 정도 푼 상태에서, proc(0,1)을 호출합니다.

이 때 cache[0][0]에는 반 정도의 경우의 수만 고려한 최적이 아닌 답이 들어가 있습니다.

그런데 proc(0,1) 입장에서는 cache[0][0] 가 -1이 아니므로 (0,0)의 문제를 전부 푼걸로 생각해서, 이 잘못된 답을 사용하여 답을 구합니다.

그렇게 cache[0][1]에는 미완성된 답인 cache[0][0]을 이용했으므로 잘못된 답이 들어가고,

proc(0,0)이 호출했던 proc(0,1) 역시 이 잘못된 값을 리턴하여 cache[0][0]도 결국 제대로 답을 구해낼 수 없습니다.

sourish92   2년 전

답변 주신 모든 분들, 답변 정말 감사합니다!

@Green55 님 설명을 듣고 확실히 이해가 되었습니다.

부분문제관의 의존성을 따져봤을 때, 사이클이 존재하는 경우 DP를 이용할 수 없다는 사실을 처음 알았네요..

열심히 공부하겠습니다. 감사합니다 ㅎㅎㅎㅎㅎ

sourish92   2년 전


@djm03178 님 관련된 비슷한 질문글에 행과 열을 이용한 DP로는 풀 수 없다고 하셨는데..

그럼 혹시 다른 고려사항을 추가한다면 DP로도 풀 수 있는건가요?

djm03178   2년 전

https://www.acmicpc.net/board/... 이 댓글을 말한 것이었는데, BFS에 비해 매우 비효율적입니다.

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