[Python] 1199번 오일러 회로

https://www.acmicpc.net/problem/1199

---

 

24/09/01

 

 

오일러 경로 기본 문제이다. 알고리즘은 간단했으나 시간이 좀 빡빡해서 몇 번의 최적화를 거친 후에야 맞았습니다를 받을 수 있었다.

---

 

문제 접근 방식:

 

 

무방향 연결 그래프에서 오일러 경로는 정점의 차수가 홀수인 정점이 $0$개이거나 $2$개일 때 만들어 질 수 있다.

 

차수가 홀수인 정점이 $0$개인 경우, 어느 점에서 시작을 하던 간에 다시 그 점으로 돌아오는 오일러 "회로"를 만들 수 있다.

 

차수가 홀수인 정점이 $2$개인 경우, 차수가 홀수인 $A$ 정점에서 시작하여 차수가 홀수인 $B$ 정점으로 도착하는 오일러 경로를 만들 수 있다.

 

이 문제는 오일러 "회로"가 만들어지는 조건을 물어보고 있으며, 그것이 가능한 경우 그 경로를 출력할 것을 요구하고 있다.

 

오일러 "회로"가 만들어지는 경우는 위에 써놓은 것과 같이 쉽게 판단할 수 있다.

 

만약 만들어진다면, 임의의 점을 기준으로 잡고 오일러 경로를 그으면 회로가 만들어지므로 이를 출력하면 된다.

 

 

문제의 핵심 부분은 오일러 경로를 실제로 구현하는 부분에 있다.

 

구현의 방식은 다음과 같다.

 

1. 현재 인접 행렬에서 간선이 존재하는 경우, 그 간선으로 간다. 그리고 간선을 지워준다. 인접 행렬의 값을 1 감소시킴으로서 구현할 수 있다. 새로운 정점으로 가는 경우 재귀를 통해 더 탐색해준다.

 

2. 더 이상 현재 정점에서 갈 수 있는 간선이 존재하지 않는 경우 도착한 것이다. 따라서 이 정점을 Path에 추가한다.

 

이렇게 구현한다면 $A$에서 시작해서 $B$로 도착하는 오일러 경로를 '역순'으로 구할 수 있다. 하지만 여기서는 오일러 회로를 구하는 것이므로 상관이 없다.

 

나이브한 구현은 다음과 같다.

 

# 1199번 오일러 회로
# 오일러 경로
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1_000_000)

path = []
def eulerpath(graph, now, N):
    for i in range(N):
        if graph[now][i]:
            graph[now][i] -= 1
            graph[i][now] -= 1
            eulerpath(graph, i, N)
    path.append(now+1)

def main():
    N = int(input())
    graph = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        degree = 0
        for j in range(N):
            degree += graph[i][j]
        if degree % 2:
            print(-1)
            return
    eulerpath(graph, 0, N)
    print(*path)
    
main()

 

참고로 위의 구현은 이 문제에서 시간초과를 받는다.

 

재귀함수를 사용했기 때문에 sys.setrecursionlimit을 통해 재귀 깊이를 늘려주는 것이 필수이며, 이는 시간 초과와 메모리 초과로 직결된다.

 

또한, 한 정점에서 다른 정점으로 간선을 타고 갈 때, $\mathcal{O}(V)$가 소요되므로 매우 느리다고 할 수 있다.

 

 

따라서 두 가지 부분에서 최적화를 진행했다.

 

1. 재귀함수 대신 스택으로 DFS진행.

 

2. 한 정점에서 다른 정점으로 간선을 타고 갈 때 $\mathcal{O}(1)$이 소요되도록 graph를 딕셔너리로 관리. 이를 통해 한 정점에서 다른 정점으로 갈 때 $\mathcal{O}(1)$이 소요된다.

 

$graph[i]$는 딕셔너리이고, $graph[i][j]$는 $i$번 정점과 $j$번 정점 사이의 간선의 개수를 저장한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1199번 오일러 회로
# 오일러 경로
import sys
input = sys.stdin.readline

def eulerpath(graph, now, N):
    stack = []
    stack.append(now)
    path = []
    while stack:
        now = stack[-1]
        if graph[now]:
            for near, cnt in graph[now].items():
                graph[now][near] -= 1
                graph[near][now] -= 1
                if graph[now][near] == 0:
                    graph[now].pop(near)
                    graph[near].pop(now)
                stack.append(near)
                break
        else:
            path.append(now+1)
            stack.pop()
    return path

def main():
    N = int(input())
    adj = [list(map(int, input().split())) for _ in range(N)]
    graph = [dict() for _ in range(N)]
    for i in range(N):
        degree = 0
        for j in range(N):
            degree += adj[i][j]
            if adj[i][j]:
                graph[i][j] = adj[i][j]
        if degree % 2:
            print(-1)
            return
    print(*eulerpath(graph, 0, N))
        
main()