프로그래민👨‍💻

해밀턴 순환회로, A정점에서 시작하여 모든 정점을 최소비용으로 돌아 A정점으로 돌아오는 문제이다. 다른 말로는 TSP, 외판원 순환 문제라고 한다. 이 문제는 다양한 풀이 방법으로 접근 할 수 있지만 N의 값이 12 이하로 주어졌으므로 백트래킹을 이용한 완탐을 사용해보았다. 단, 순열의 완탐을 돌때 첫번째 점(0)을 제외한 N-1개의 순열을 구하고 이때 마지막에 해당하는 점에서 첫번째점(0)으로의 경로가 존재하는 경우 최종답을 확인해주는 방식으로 구해준다. 또한 방문시에 최저값을 갱신할수 있을때만 방문하는 조건을 사용하여 시간을 줄였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3..

TSP문제 이다. N의 범위가 10이하이므로 순열을 사용하여 풀었다. perm라는 순열을 구하는 함수를 작성하였다. 여기서 arr라는 배열을 준비하여 각 인덱스 마다 도시의 번호로 지정하고, result라는 배열을 이용하여 도시들을 방문하는 경우의 수를 구하였다. result 배열이 전부 준비되었을 때 서로 도시끼리 갈 수 있는지 여부를 체크하면서 최종적으로 돌아오는 경우까지 계산하여 최종 답을 구하였다. 이 문제는 생각을 달리한다면 시간복잡도를 줄일 수 있는데, 그 경우는 시작 지점을 고정시키는 개념이다. 즉 0 1 2 3 4 0 과 1 2 3 4 0 1 은 동일한 연산이므로 첫번째 시작지점을 고정시켜서 동일한 계산을 반복안하게 하는 방법으로 시간복잡도를 줄일 수 있다. 1 2 3 4 5 6 7 8 9..