Yet Another Hamiltonian Path Problem

정점 $1$에서 $A_1=0$이면 나가는 간선이 하나도 없다. 따라서 해밀턴 경로가 존재한다면 정점 $1$은 경로의 마지막 정점이어야 한다.

마찬가지로 정점 $N$에서 $A_N=1$이면 나가는 간선이 하나도 없다. 따라서 이 경우 정점 $N$도 경로의 마지막 정점이어야 한다.

따라서 $A_1=0$이고 $A_N=1$이면 서로 다른 두 정점이 모두 마지막 정점이어야 하므로 해밀턴 경로가 존재하지 않는다.

이제 나머지 경우에는 항상 해밀턴 경로를 직접 만들 수 있다.

$A_N=0$이라고 하자. $A_i=1$인 정점을 번호의 오름차순으로 모두 출력한 뒤, $A_i$인 정점을 번호의 내림차순으로 모두 출력한다. 첫 번째 부분에서는 현재 정점의 값이 이고 다음 정점의 번호가 더 크므로 항상 간선이 존재한다. 두 번째 부분에서는 현재 정점의 값이 이고 다음 정점의 번호가 더 작으므로 항상 간선이 존재한다. 두 부분이 모두 비어 있지 않다면 첫 번째 부분의 마지막 정점 번호는 보다 작고, 두 번째 부분의 첫 정점은 이다. 따라서 두 부분 사이에도 간선이 존재한다.

$A_N=1$이라면 불가능한 경우가 아니므로 $A_1=1$이다. 이때는 $A_i=$인 정점을 번호의 내림차순으로 모두 출력한 뒤, 인 정점을 번호의 오름차순으로 모두 출력한다. 각 부분 내부의 간선은 앞의 경우와 같은 이유로 존재한다. 두 부분이 모두 비어 있지 않다면 첫 번째 부분의 마지막 정점 번호는 보다 크고, 두 번째 부분의 첫 정점은 이므로 두 부분 사이에도 간선이 존재한다.

각 정점을 상수 번만 확인하므로 테스트 케이스 하나의 시간복잡도는 $O(N)$이고, 전체 시간복잡도는 $O(\sum N)$이다. 추가 공간복잡도는 $O(N)$이다.

Solution written by GPT5.6