글 읽기 - 메모리 초과 나는 이유가 뭘까요?

hsw0194 2년 전 0

시작하자마자 메모리초과가 나는데

어떤 부분에서 나는지를 모르겠습니다.

다 필요한 부분같은데 어렵네요..

from sys import stdin, setrecursionlimit
from collections import defaultdict

# 1<=V<=10^3
# 0<=E<=10^7
# T(dfs:adjacent list) => O(E+V)
# T(dfs)*V => O(V(E+V)) = O(EV+V^2) = O(EV=10^10) -> TLE

# T(dfs:adjacent matrix) => O(V^2)

# if S->Snext-*>Q-*>P-*>Sprev->S exists,
# then Q-*>P-*>Sprev->S->Snext-*Q exsits.

N = int(stdin.readline())
setrecursionlimit(1000000)


def sol():
    connections = []

    for _ in range(N):
        connections.append(list(map(int, stdin.readline().split())))

    for i in range(N):
        if sum(connections[i]) % 2 == 1:
            print(-1)
            return

    how_many_edges = sum(sum(connections, [])) // 2  # O(V^2)

    adjacent_list = defaultdict(list)  # S : O(V^2)

    for i in range(N):  # O(V^2)
        for j in range(N):
            if i == j: continue
            if connections[i][j] > 0:
                adjacent_list[i].append(j)  # 평균적으로 O(1)

    def dfs(node, connections):  # O(V^2)?
        nonlocal how_many_edges

        # 현재 노드에서 인접한 것들 중에서
        for adjacent in adjacent_list[node]:  # O(V)
            # 아직 인접노드까지의 edge가 있다면
            if connections[node][adjacent] > 0:
                # 노드 개수를 하나 감소시키고
                connections[node][adjacent] -= 1  # O(1)
                connections[adjacent][node] -= 1  # O(1)
                '''
                # 다음에 E개의 edge를 모두 방문한다는건 무조건 돌아왔다는 뜻
                if count + 1 == how_many_edges and ori == adjacent:
                    trace.append(ori)
                    if not flag:
                        print(' '.join(map(str, map(lambda x: x + 1, trace))))
                        # print(c)
                        flag = True
                    return
                '''

                dfs(adjacent, connections)
                ''' 
                # 어차피 경로가 있음이 보장됨
                connections[node][adjacent] += 1
                connections[adjacent][node] += 1
                '''
        print(node + 1, end=" ")

    dfs(0, connections)


sol()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과 나는 이유가 뭘까요?

hsw0194 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말