[SWEA] 1247. 최적 경로 -DP

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE

문제를 읽고 짧은 시간 안에 해결해야 하는 문제인줄 알고 겁부터 먹었지만

모든 가능한 경로를 살펴서 해를 찾아도 좋다기에

신나는 마음으로 완전 탐색을 적용할 생각을 했습니다. ㅎㅎ

문제 형태를 보아하니 주로 쓸 함수를

이렇게 정의하면 좋을것 같더라고요. ㅎㅎ

visited에는 현재까지 방문한 고객들을 비트마스크를 이용해서 표현하고, last는 마지막으로 방문한 고객의 index를 표현합니다.

반환하는 값은 집으로까지 가는데 필요한 최소 경로입니다.

이렇게 정의하고 나면 문제에서 시간을 넉넉하게 주긴 했지만 cache를 이용하고 싶더라고요.

그래서

이런 cache도 정의해서 사용했습니다. ㅎㅎ n이 최대 10이고, 회사랑 집을 포함하면 총 12개의 상태를 저장해야 하므로

visted가 최대 2^12인데 넉넉하게 4100으로 했습니다.

실행 시간을 계산해보니

일단 완전 탐색의 실행시간은 O(n!)이 됩니다.

방문하는 고객의 집을 정렬하는 것과 같은 만큼 소요 되죠.

n이 최대 10이므로 n!은 해봤자 400만정도입니다. 10초안에는 충분히 실행할 수 있죠.

주로 쓸 함수의 정의 내용입니다.

nextStep은...나중에 디버깅하느라 만든 2차원 배열입니다.

visited와 last가 주어졌을때 어떤 고객의 집을 선택하면 최소경로로 갈 수 있는지 저장합니다.

아래는 제 코드 전문입니다 ㅎㅎ

http://colorscripter.com/s/05LdtmE