Traveling Salesperson Probelm

2회차 문제 풀이 복기

2번째 푸는 것인데도 문제가 낯설게 느껴졌지만! 순열을 이용하여 푼다는 것을 깨닫고 차근히 풀어나가봤다!

알고리즘 생각

첫번째 순열 : 오름차순 마지막 순열 : 내림차순

1234에서 사전증가순 다음 순열은 1243이 된다. 이렇게 직관적으로 찾은 이유는 끝에서부터 a[i-1]<a[i]인 i를 찾아야한다!

틀린 부분(틀린 이유)

1. 배열범위초과 a[i-1]과 a[i]를 비교하는 것이기 때문에 i는 0보다 크다고 해주어야 배열 범위를 벗어나지 않는데 i>=0으로 해서 i가 0이 될 때까지 진행해버려 a[i-1]가 배열범위를 벗어나 에러가 났다.

int i=a.length-1;//끝에서부터 시작!a[i-1]<a[i]인 i를 끝에서부터 찾는다!
while(i>0 && a[i-1]>=a[i]) {
		i--;
}

2. 스코프 문제 do-while문은 next_permutation(d)의 다음 순열이 true인 동안 계속해서 실행되며 다음 순열을 생성한다. do-while문을 반복하면서 생성되는 각 순열에 대해 순회 비용과, 유효성 검사를 초기화해주어야하는데 sum과 ok를 do-while문 밖에 두어 초기화를 해주지 않아서 오답이 나왔다. 원래 최소비용 정답은 35인데 오답으로 39가 나왔다. 그 이유는 sum을 초기화하지 않고 계속 더해갔기 때문이다. 첫번째 순회 비용은 39이고 그 다음 순열의 순회 비용이 35라서 정답은 35가 나와야하지 39+35=74, 74+x+x2....가 sum은 계속적으로 더해진다. 첫 번째 순회 비용이 최솟값이 아님에도 불구하고 sum은 계속 더해지기 때문에 첫번째 순회 비용이 정답으로 나왔다.

3. while 조건문 설정 i와 j가 같으면 재정렬할 필요 없지만 그렇지 않은 경 a[i-1]과 a[j]를 바꾼 후 i보다 작은 a[i-1]이 i의 뒤에 왔으니 i 뒤의 숫자들을 오름차순으로 재정렬해주어야한다. j는 끝에서부터 시작하고, a[i]와 a[j]를 바꾸어준다. i는 1씩 증가, j는 1씩 감소시킨다. 이 연산을 언제까지 반복해야하는가? 1)i가 j와 같아질 때까지(i와 j가 다르면 계속 반복) : while(i!=j) => i++,j-- 결국 배열범위 초과한다! 2)i++<n && j-->=0 : i뒤의 숫자들만 swap해서 재정렬하면되는데 전체 숫자들을 다 바꿔버리게 된다! 그렇다면 반복조건은 무엇인가? 생각을 해보면 i<j인 상황에서 a[i]<=>a[j]하고 i++,j-- 하다가 j < i가 되면 정렬이 완료되어 그만하면 된다! 그렇다면 i<j인 동안에만 반복해주면되기 때문에 while 반복 조건은 while(i<j) 가 된다!

//while(i!=j) 이렇게 하면 i는 계속 증가해서 배열범위밖, j는 계속 감소해서 배열범위밖이 된다!
		//while(i<a.length && j>=0) {//반복 조건 : j는 length-1인데 a[i]>a[j]이면 오름차순으로 바꿔줘야함!
		while(i<j) {//현재 i<j인 상황.i++,j--	해서 j<i 가 되면 그만!
			tmp=a[i];
			a[i]=a[j];
			a[j]=tmp;
			i++;j--;
		}