소프티어

def dfs(node,graph,visited):
    if visited[node]:
        return

    visited[node] = True

    for nx in graph[node]:
        dfs(nx, graph, visited)


visitedS = [False for _ in range(n+1)]
visitedS[t] = True
dfs(s, graph, visitedS)

visitedRS = [False for _ in range(n+1)]
dfs(t, graphR, visitedRS)

visitedT = [False for _ in range(n+1)]
visitedT[s] = True
dfs(t, graph, visitedT)

visitedRT = [False for _ in range(n+1)]
dfs(s, graphR, visitedRT)

소스 코드의 일부입니다. dfs를 이렇게 구현했을 경우에는

40-2 케이스에서 실행시간은 1181.0ms, 메모리는 202.28mb 가 나옵니다.

하지만 이를 아래처럼 변경하면,

def dfs(node,graph,visited):

    for nx in graph[node]:
        if visited[nx]:
            continue
        visited[nx] = True
        dfs(nx, graph, visited)


visitedS = [False for _ in range(n+1)]
visitedS[t] = True
visitedS[s] = True
dfs(s, graph, visitedS)

visitedRS = [False for _ in range(n+1)]
visitedRS[t] = True
dfs(t, graphR, visitedRS)

visitedT = [False for _ in range(n+1)]
visitedT[s] = True
visitedT[t] = True
dfs(t, graph, visitedT)

visitedRT = [False for _ in range(n+1)]
visitedRT[s] = True
dfs(s, graphR, visitedRT)

40-2 케이스에서 실행시간은 2041.0ms, 메모리는 1024mb로 메모리 초과가 납니다.

로직 상으로는 둘 다 동일 한 것 같은데, 왜 이러한 결과가 나왔는 지 알 수 있을까요?

* 저는 처음에 캐시의 공간 지역성 때문에, visited[nx]를 할 때마다 cache miss가 발생하여 속도가 느려졌다고 생각했었습니다. 하지만 메모리 사용량이 1024mb인 것을 보면 공간 지역성은 상관이 없는 것 같습니다... ㅠㅠ