zealtez   4달 전

최소 비용이 잘 나오는 것 같은데 어디가 잘못 된건지 계속 틀리네요.

좋은 지적 부탁드립니다.

kalmiaa   4달 전

출발위치를 N만큼 잡으셔서, 한번씩 다 돌려봐야 합니다.

zealtez   4달 전

혹시, 어느 지점에서 시작해도 최소비용은 같지 않나요??

kalmiaa   4달 전

지금 문제에서는 v1 -> v2 의 비용과 v2->v1의 비용이 다릅니다.


그러므로 다 돌려야 합니다.

몇 가지 손으로 그리시다보면 반례를 찾으실 수 있으실겁니다.

kalmiaa   4달 전

아 그리고 지금처럼 dfs로 돌리시면 무조건 timeout 납니다.


brute force거든요. 

n! 복잡도로 가고 있습니다.


외판원 dp 검색하시면 많이 나올거에요. bit 기초연산 + dp로 n 12인가? 14정도까지 풀 수 있을거에요.

zealtez   4달 전

(도시의 수) N이 10이하라서 완전 탐색을 이용해서 풀어보고 싶었는데

조언을 바탕으로 DP로 수정해야겠네요. 많은 조언 감사합니다 !!

plzrun   4달 전

kalmiaa

dfs로 해결할 수 있습니다. n제한이 10밖에 안되니까 10!은 300만 정도.. 그럼 가능합니다. 그렇게 해서 풀기도 했구요

plzrun   4달 전

그리고 모든 시작점에서 테스트해보지 않아도 됩니다.

어차피 최단 경로는 유일하기 때문에 어느점에서 시작해도 최단경로를 찾을 수 있으니까..

그냥 아무 번호에서나 시작하고 그 시작지점으로 돌아오는지만 확인하면 됩니다.

plzrun   4달 전

그리고 질문작성자님 간선이 0일때는 길이 없는거를 체크안해주신거 같아요.

확인해보세용 ㅎ

zealtez   4달 전

부족한 부분을 잘 알게되었습니다. ㅎ

plzrun님 kalmiaa님 상세한 답변 감사합니다.

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