[알고리즘][백준 1199] 오일러 회로

문제 링크

백준 1199 오일러 회로 링크

문제 풀이

기본적인 문제 풀이 알고리즘은 다음과 같다.
1. 어떤 한점(=x지점)에서 DFS를 시작한다.
2. x지점과 연결되어있는 모든 지점으로 DFS를 다시 진행 한다. 그리고 한번 간 간선은 다시 이용 못하므로 이용했다고 체크해둔다.
3. 특정 지점에서 모든 곳으로 연결을 확인하면 확인이 끝나는 순간 그때의 지점을 출력한다.

중요한 점

중요한 점은 언제 출력하는 것이다. 이 문제는 단순히 오일러 회로의 조건에 만족하는지 아닌지를 확인하는 문제가 아니라, 조건에 만족할 경우 그 경로를 출력해야 한다. 그렇기 때문에 언제 출력할지 잘 생각해야한다.
나는 이 것이 어려워서 구글링을 해서 답을 얻을 수 있었다. 바로 DFS함수가 끝나는 순간 출력하면 된다.

또 중요한 점이 C++과 자바와는 다르게 파이썬은 재귀의 깊이를 사용자가 지정해 줘야한다. 따라서 코드의 윗부분에 sys.setrecursionlimit(10**9)처럼 해줘야 한다.

마지막으로 또 다른 언어와의 차이인데 C++과 자바보다 파이썬이 느리다는 것을 느꼈다.
그 이유가 C++과 자바로 이 문제를 푼 코드를 보면, 특정 지점에서 그 지점과 연결된 점들을 찾기 위해서 입력에서 받아온 2차원 행렬을 그대로 search한다.
무슨 말이냐면, 예를 들어
6
0 1 0 1 1 1
1 0 1 1 1 0
0 1 0 1 0 0
1 1 1 0 1 0
1 1 0 1 0 1
1 0 0 0 1 0
이와같은 예시 입력이 주어졌을때, 0번째 노드는 1, 3, 4, 5번째 노드와 연결되어있다. 이를 위해서 for문을 돌면서 연결이 되었는지 아닌지 확인한다.

하지만 파이썬은 다른 언어보다 느리기 때문에 여기서 시간을 단축해야 한다. 그러기 위해서 graph라는 딕셔너리를 만들고, 해당 키값의 value값들에 그 키값에 연결되어있는 노드들을 저장한다. 예를들어, 키가 0인 graph의 value는 1,3,4,5이다. 이렇게 하면, 0번째 노드와 2번째 노드는 확인을 안할 수 있어서 시간이 단축된다.

코드

import sys
sys.setrecursionlimit(10**9)

N=int(sys.stdin.readline())

myList=[]

for i in range(N):
    myList.append(list(map(int,sys.stdin.readline().rstrip().split())))

graph={}

for i in range(N):
    graph[i]=[]
    rowSum=0
    for j in range(N):
        for k in range(myList[i][j]):
            rowSum+=1
            graph[i].append(j)
    if rowSum%2==1:
        print(-1)
        sys.exit()

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

dfs(0)