> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/traveling-salesperson-probelm.md).

# Traveling Salesperson Probelm

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

알고리즘 생각

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

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

**틀린 부분(틀린 이유)**

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

```java
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)** 가 된다!

```java
//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--;
		}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/traveling-salesperson-probelm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.