[백준]1199 오일러회로

1. 풀이

* 오일러 경로 : 모든 edge를 정확히 1번만 방문하는 연속된 경로

<=> 차수가 홀수인 정점이 2개(출발점과 도착점은 각각 차수가 홀수개)

​

* 오일러 회로 : 오일러 경로 중 시작점과 끝점이 같은것

<=> 차수가 홀수인 정점이 0개(나갔으면 들어오는 점(or 들어왔으면 나가는점)이 있어야 함)

​

오일러 회로를 구하는 문제이므로 (1) 모든 정점에서 차수가 짝수임을 확인하고 ​(2)짝수임이 확인되었으면 반드시 오일러 회로가 (어느 정점에서 시작하든) 가능하므로 아무정점이나 시작점으로 잡고 dfs돌림.

​

(2) dfs를 돌릴 때

- 어느방향으로 돌리든 답은 나온다. 따라서 L[nowNode][conNode]-=1을 해주고 다시 +=1을 해줄 필요가 없다. 즉 탐색은 무조건 edge의 개수만큼 한다.

(만약 +=1을 해주고 다시 재귀적으로 모든 경우를 탐색 하면 시간초과가 난다. 소스코드1)

- for문이 끝난 뒤 마지막에 print해주면 자연스럽게 마지막탐색한 것 부터 차례대로 출력이 된다.

( 마치 유향그래프의 사이클확인 시 fin과 같다. https://blog.naver.com/ngoodsamari/221607542218 )

- 마지막부터(dfs탐색 순서와 반대로)출력해도 결국 오일러 회로를 만족하므로 하므로 상관없다

( ex) 1->3->5->2->1 이나 1->2->5->3->1 이나 똑같이 오일러 회로이다. )

​

2.소스코드

(1) 소스코드1 (메모리초과)

import sys
sys.setrecursionlimit(10**9)

N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int,input().split())))

edge=0
graph={}
for i in range(N):
    graph[i]=[]
    rowSum=0
    for j in range(N):
        for _ in range(L[i][j]):
            rowSum+=1
            graph[i].append(j)
    if rowSum%2==1:
        print(-1)
        sys.exit()
    else:
        edge+=rowSum
edge=edge//2

def plus(num):
    return num+1

def dfs(route,size):
    nowNode=route[size-1]
    if size-1==edge and nowNode==0:
        ans=list(map(plus,route))
        print(*ans)
        sys.exit()
    for conNode in graph[nowNode]:
        #연결되어 있을때
        if L[nowNode][conNode]==1:
            L[nowNode][conNode]=0
            L[conNode][nowNode]=0
            dfs(route+[conNode],size+1)
            L[nowNode][conNode]=1
            L[conNode][nowNode]=1


dfs([0],1)
print(-1)

 

(2) 소스코드2 (통과)

import sys
sys.setrecursionlimit(10**9)

N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int,sys.stdin.readline().rstrip().split())))

edge=0
graph={}
for i in range(N):
    graph[i]=[]
    rowSum=0
    for j in range(N):
        for _ in range(L[i][j]):
            rowSum+=1
            graph[i].append(j)
    if rowSum%2==1:
        print(-1)
        sys.exit()
    else:
        edge+=rowSum
edge=edge//2

def dfs(nowNode):
    for conNode in graph[nowNode]:
        if L[nowNode][conNode]:
            L[nowNode][conNode]-=1
            L[conNode][nowNode]-=1
            dfs(conNode)
    print(nowNode+1,end=" ")

dfs(0)