해밀턴 순환에서 방문 기록을 복사할지 되돌릴지

모든 정점을 정확히 한 번씩 지나 출발점으로 돌아오는 경로를 찾는다. 오일러 회로가 간선을 다 쓰는 것이었다면 이쪽은 정점을 다 쓴다.

def hcp(i, visited=[]):
    visited.append(i)

    if len(visited) == node:
        if adj[i][start] == 1:
            ans.append(visited)
        return

    for j in range(node):
        if adj[i][j] and j not in visited:
            hcp(j, visited.copy())

정점을 다 쓰는 문제라 방문 기록이 정점 단위다. j not in visited 한 줄로 걸러진다.

마지막에 한 번 더 확인한다

if len(visited) == node:
    if adj[i][start] == 1:
        ans.append(visited)

정점을 전부 지났다고 끝이 아니다. 마지막 정점에서 출발점으로 돌아가는 간선이 있어야 순환이 된다. 그 간선이 없으면 경로이긴 해도 순환은 아니다.

오일러 쪽에서는 i == 0 으로 출발점에 실제로 도착했는지를 봤는데, 여기서는 도착하지 않고 간선이 있는지만 확인한다. 마지막 한 칸을 실제로 밟지 않는 셈이다.

되돌리는 대신 복사한다

hcp(j, visited.copy())

같은 폴더의 오일러 회로 코드는 adj 를 고쳤다가 되돌리고 path.pop() 으로 경로도 되돌린다. 여기서는 되돌리는 코드가 없다. 대신 내려갈 때마다 방문 목록을 복사한다.

각자 자기 사본을 들고 가므로 형제 가지끼리 서로 영향을 주지 않는다. 되돌릴 시점을 신경 쓰지 않아도 된다.

대신 정점 수만큼 긴 리스트를 노드마다 만든다. 되돌리는 방식은 리스트 하나를 계속 쓰고 append 와 pop 만 한다.

ans.append(visited) 에서 복사 없이 그대로 넣을 수 있는 것도 이 방식이라 가능하다. 되돌리는 방식이었다면 그 리스트가 나중에 바뀌므로 visited.copy() 로 넣어야 한다. 실제로 오일러 쪽 코드는 path.copy() 를 쓰고 있다.

기본 인자에 리스트를 둔 것

def hcp(i, visited=[]):

파이썬에서 기본 인자는 함수를 정의할 때 한 번 만들어져 호출 사이에 공유된다. 보통은 이것 때문에 문제가 생긴다.

여기서는 최상위 호출 hcp(start) 한 번만 기본값을 쓰고, 재귀 호출은 전부 visited.copy() 를 명시적으로 넘긴다. 그래서 공유된 리스트가 자라지 않는다. 같은 스크립트에서 hcp 를 두 번 부르면 그때는 어긋난다.

결과

정점 8개짜리 그래프에서 12개가 나온다.

0 1 2 4 5 7 6 3
0 1 2 5 4 7 6 3
0 1 4 2 5 7 6 3

start = 0 으로 고정해서 0에서 시작하는 것만 센다. 같은 순환을 반대 방향으로 도는 것은 따로 세어지므로 실제 서로 다른 순환은 이보다 적다.