외판원 다다스

방문 순서의 $i$번째 위치에 놓을 마을을 다음과 같이 선택한다.

• $i$가 홀수라면 아직 방문하지 않은 마을 중 $Y$좌표가 가장 작은 마을을 선택한다.
• $i$가 짝수라면 아직 방문하지 않은 마을 중 $X$좌표가 가장 작은 마을을 선택한다.

이 방법으로 항상 올바른 순서를 얻는다. $i$가 홀수라고 하자. $P_i$를 선택할 때 $P_{i+1}$은 아직 방문하지 않은 마을이므로, $P_i$의 $Y$좌표가 최소라는 사실과 모든 $Y$좌표가 서로 다르다는 사실에서 $Y_{P_i}<Y_{P_{i+1}}$가 성립한다. $i$가 짝수인 경우에도 같은 논리로 $X_{P_i}<X_{P_{i+1}}$가 성립한다. 따라서 모든 이동 조건이 만족되며, 답은 항상 존재한다.

각 좌표는 $1$부터 $N$까지의 정수를 정확히 한 번씩 사용한다. $X$좌표가 $v$인 마을과 $Y$좌표가 $v$인 마을을 각각 배열에 저장한다. 아직 방문하지 않은 마을이 나올 때까지 최소 좌표 포인터를 증가시키면, 두 포인터는 각각 최대 $N$번만 증가한다. 따라서 전체 시간 복잡도는 $O(N)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6