P5 치고 상당히 어려웠다
알고리즘 자체보다는 메모리랑 시간초과가 상당히 빡빡해서 최적화 작업이 꽤나 빡셌다.
데이터 추가되고 급 난이도 상승되어서 재채점 결과보니 상당수가 갈려나간걸 볼 수 있었다.
데이터 추가 1/10이 갈려나감 ;; 데이터 추가 되고 난이도 평가가 올라갔다.
오일러 회로란 모든 간선을 순회하면서 시작 지점과 끝 지점이 같은 경로를 말한다.
한붓그리기가 가능하며 , 모든 정점의 간선 개수가 짝수개여야지만 성립이 가능하다.
DFS 순회를 돌면서 가장 먼저 완료되는 정점부터 기록을 하면 그게 바로 오일러 회로가 된다.
단순 재귀나 스택으로 DFS 순회를 돌면 시간초과나 메모리 초과가 뜰 것이다.
최적화 작업을 위해서 간선을 루프를 돌릴 때 이미 방문이 끝난 간선은 제거해야 했다.
간선을 제거하기 위해 그래프를 Hash로 저장을 했으며 O(1)의 시간으로 간선을 제거할 수가 있다.
따로 Visit[i][j] 배열을 만들어서 i,j로 가는 간선의 개수를 저장을 했으며
list와 dict의 접근 시간복잡도가 O(1)으로 같다고 해도 시간이 dict가 조금 느리기 때문에 따로 visit을 만들었다.
while stack 루프를 돌면서
방문한 점을 스택에 저장하고
현재 정점에서 아직 갈 수 있는 다음 정점 하나를 스택에 추가를 한다.
현재 정점에서 갈 수 있는 간선이 없으면 stack에서 pop 한다음 정답에 추가를 했다.
52트만에 겨우 성공했다!
import sys
from collections import defaultdict
n = int(input())
input = sys.stdin.readline
graph = []
degree = [0] * n
visit = [[0] * n for _ in range(n)]
for i in range(n):
lst = {}
for j, v in enumerate(list(map(int, input().split()))):
if v:
lst[j] = 1
visit[i][j] = v
degree[i] += v
graph.append(lst)
for i in range(n):
if degree[i] % 2:
print(-1)
sys.exit()
answer = []
stack = [0]
while stack:
current = stack[-1]
if graph[current]:
_next = next(iter(graph[current]))
visit[_next][current] -= 1
visit[current][_next] -= 1
degree[current] -= 1
degree[_next] -= 1
if not visit[current][_next]:
del graph[current][_next]
del graph[_next][current]
stack.append(_next)
else:
answer.append(stack.pop() + 1)
for i in range(n):
if degree[i]:
print(-1)
sys.exit()
print(' '.join(map(str, answer)))
