해밀턴 회로

정점이 $N$개, 간선이 $N(N-1)/2$개인 방향 그래프 $G$가 있다. 정점 번호는 0부터 $N-1$까지다. 서로 다른 두 정점 $i$와 $j$ 사이에는 $i$에서 $j$로 가는 간선과 $j$에서 $i$로 가는 간선 중 정확히 하나만 있다. 따라서 간선의 방향을 무시하면 $G$는 완전 그래프다.

$X$는 $G$의 인접 행렬이다. $X_{i,j}$가 +이면 $i$에서 $j$로 가는 간선이 있고, -이면 없다. $X_{i,i}$는 항상 .이다.

$G$의 해밀턴 회로는 $G$의 모든 정점을 한 번씩 지나는 길이 $N$짜리 사이클이다. $G$가 주어지면 해밀턴 회로가 있는지 판정하고, 있으면 하나를 출력한다.

첫째 줄에 정점의 개수 $N$이 주어진다. 둘째 줄부터 $N$개의 줄에 인접 행렬 $X$가 주어진다. 이 중 $i$번째 줄의 $j$번째 문자가 $X_{i,j}$이다.

$G$에 해밀턴 회로가 없으면 -1을 출력한다.

있으면 해밀턴 회로가 지나는 정점 $N$개를 지나는 순서대로 공백 하나로 구분해 출력한다. 해밀턴 회로가 여러 개일 수 있으므로, 아래 절차가 만드는 회로를 그대로 출력한다.

서로 다른 정점을 담은 수열 $c_0, c_1, \dots, c_{k-1}$을 유지한다. 이 수열은 사이클 $c_0 \to c_1 \to \dots \to c_{k-1} \to c_0$을 뜻하고, $(c_{k-1}, c_0)$을 포함해 이웃한 모든 쌍은 $G$의 간선이다. 정점 0 하나만 담은 수열에서 시작해, 수열이 정점 $N$개를 모두 담을 때까지 다음을 반복한다. 수열에 없는 정점을 자유 정점이라고 부른다.

1. 어떤 자유 정점 $v$에 대해 수열의 정점에서 $v$로 가는 간선과 $v$에서 수열의 정점으로 가는 간선이 모두 있으면, 그런 $v$ 중 가장 작은 것을 고른다. $X_{c_i,v}$가 +이고 $X_{v,c_{(i+1) \bmod k}}$가 +인 가장 작은 첨자 $i$를 찾아 $v$를 $c_i$ 바로 뒤에 넣는다. 그런 $i$는 항상 있다.
2. 그렇지 않으면 자유 정점 쌍 $(w, u)$ 중에서 수열의 모든 정점에서 $w$로 가는 간선이 있고, $u$에서 수열의 모든 정점으로 가는 간선이 있으며, $w$에서 $u$로 가는 간선도 있는 쌍을 모은다. 그중 사전순으로 가장 작은 쌍을 골라 수열 끝에 $w$, $u$ 순서로 덧붙인다.

$G$에 해밀턴 회로가 있으면 매 단계에서 두 규칙 중 하나가 반드시 적용되고, 수열의 맨 앞은 계속 정점 0이므로 출력하는 회로는 정점 0에서 시작한다.

• $3 \le N \le 1\,000$