[SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

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

---

"이 문제는 가장 짧은 경로를 '효율적으로' 찾는 것이 목적이 아니다."

라는 것을 보아하니 모든 경로를 방문하는 dfs를 구현해서 풀어보라는 문제같다.

나는 외판원순회(TSP)로 풀었다.

N+2개의 좌표간 최단 거리를 구해서 배열에 저장해둔다.

메모이제이션을 위해 (방문한 고객 인덱스들, 현재 좌표 인덱스) 를 인덱스로 하는 배열을 하나 만든다.

이 배열에는 현재 좌표 인덱스부터 아직 방문하지 않은 고객들을 모두 방문한 후 집으로 돌아가는 경로 거리 중 최단 거리를 저장한다.

만약 모든 고객들을 방문했다면 현재 인덱스부터 집으로 돌아가는 거리를 구해서 반환한다.

즉, TSP(방문한 곳 0, ind) + (회사~ ind 고객 방문 경로 거리) 들 중 최단 거리가 정답이 된다.

---

소스코드 : https://gist.github.com/fpdjsns/67f6aa7477a9d0f424c21ff5fce25635