오일러 회로를 간선을 지웠다 되돌리며 찾기

오일러 회로는 모든 간선을 정확히 한 번씩 지나 출발점으로 돌아오는 경로다. 모든 정점을 한 번씩 지나는 해밀턴 순환과 다루는 대상이 다르다.

이 차이가 코드에서 방문 기록을 어디에 두느냐로 나타난다.

def ecp(i, path=[]):
    path.append(i)

    if i == 0 and len(path) == edge + 1:
        allpath.append(path.copy())
        return

    for j in range(node):
        if adj[i][j] == 1:
            adj[i][j] = 0
            adj[j][i] = 0
            ecp(j)
            adj[i][j] = 1
            adj[j][i] = 1
            path.pop()

정점을 방문했는지 기록하는 집합이 없다. 대신 인접 행렬 자체를 0으로 만들었다가 되돌린다.

간선을 지나면 그 간선이 사라지고, 돌아오면 살아난다. 정점은 몇 번이든 다시 지날 수 있어야 하므로 정점 쪽에는 아무 제약을 두지 않는다.

무방향이라 양쪽을 지운다

adj[i][j] = 0
adj[j][i] = 0

간선 하나가 행렬에서 두 칸을 차지한다. 한쪽만 0으로 만들면 반대 방향으로 그 간선을 또 쓸 수 있게 된다. 되돌릴 때도 두 칸을 같이 살린다.

행렬을 만들 때도 같은 이유로 양쪽에 넣는다.

adj[i][j] = 1
adj[j][i] = 1

종료 조건이 간선 수다

if i == 0 and len(path) == edge + 1:

두 가지를 같이 본다. 출발점으로 돌아왔는가, 그리고 간선을 전부 썼는가.

간선을 edge 개 지나면 정점은 edge + 1 개가 기록된다. 시작 정점이 처음에 한 번 들어가기 때문이다. 정점 수가 아니라 간선 수가 기준이라는 게 이 문제의 특징이다.

되돌리는 자리

path.pop() 이 ecp(j) 다음에 있다. 자식이 path.append 한 것을 부모가 지우는 모양이다.

답을 찾은 가지에서는 return 이 pop 앞에 있어서 그 자리에서는 안 지우는데, 부모의 반복문으로 돌아가면 거기서 지워진다. 결과적으로는 맞다.

path=[] 를 기본 인자로 둔 것도 눈에 걸린다. 파이썬에서 기본 인자는 함수를 정의할 때 한 번 만들어져 호출 전체에서 공유된다. 여기서는 append 와 pop 이 짝이 맞아 문제가 안 생기지만 의도한 공유는 아닌 것 같다. 아래에 있는 path = [] 는 이것과 다른 리스트이고 쓰이지 않는다.

결과

정점 5개, 간선 7개짜리 그래프에서 24개가 나온다.

22 [0, 4, 2, 1, 0, 3, 2, 0]
23 [0, 4, 2, 3, 0, 1, 2, 0]
24 [0, 4, 2, 3, 0, 2, 1, 0]

정점 0 과 2 가 여러 번 나온다. 정점을 다시 지나도 되기 때문이다. 대신 같은 간선 쌍은 어느 경로에도 두 번 나오지 않는다.