windy10928   5년 전

안녕하세요. 해당 문제 테스트 케이스 구해서 해보니 최대 이익과 탐색한 동굴의 수는 잘 나오는거 같은데 

경로를 찍는 부분에서 틀리는거 같습니다. 뭐가 문제인지 모르겠네요 ㅠ visited 배열로 메모이제이션 한 걸로 각 노드에 최대 이익이 나와 있고 

find() 함수에 보시면 visited[idx] - map[idx] == visited[i] - cost 에 조건에 해당하는 노드를 이전 노드로 생각하고 재귀적으로 호출해서 1까지 다시 올라갔습

니다.

무엇이 틀린걸까요 ㅠㅠ... 경로 찍는거 너무 어렵네요...

dgim92667   6달 전

이 댓글을 보실진 모르겠지만 답변 남깁니다. 결론부터 말하면 한 지점에서 다른 지점으로 갈 때의 경로를 저장하여 거꾸로 거슬러 가면 됩니다.

최대 이익을 구하셨다면 분명히 최대 이익이 되는 경로를 지났을 겁니다.

예시를 들어 설명하겠습니다.

4 4
10 20 30 40
1 2 10
2 4 20
1 3 20
3 4 10

알고리즘이 순서대로 node를 확인했다고 칩시다.

위상 정렬로 작성했을 때 알고리즘은 다음과 같은 과정을 거칩니다. 괄호 안은 이익입니다.

1 -> 2 (20)

1 -> 3 (20)

2 -> 4 (40)

3 -> 4 (50)


주목 해야 할 점은 최대 이익이 되는 경로를 구하려면 2 -> 4가 아닌 3 -> 4로 가야 합니다.

즉, 4에선 2가 아닌 3으로 가야 한다는 것으로 생각할 수도 있습니다. 따라서 4에는 3이 저장됩니다.

1 -> 2, 1 -> 3에도 위의 과정을 거치면 다음과 같은 배열을 생성할 수 있습니다. [0, 1, 1, 3]

그럼 이제 최종 경로를 어떻게 만들 수 있는지 보이시죠?


제가 말한 방법으로도 시간 초과가 나더라도, 적어도 재귀적으로 불러오는 것보단 빠를 것 같아서 답변 남깁니다.

참고로 자동차 경주라는 문제에서도 이와 똑같은 논리가 마지막에 필요하니 그 문제도 풀어보시면 좋을 것 같습니다.

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