Notice
Recent Posts
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Archives
관리 메뉴

교대최소제곱법

[백준 파이썬 21606번 아침 산책] 메모리 초과 해결 본문

코딩테스트

[백준 파이썬 21606번 아침 산책] 메모리 초과 해결

옐라크레 2023. 10. 20. 21:57

서울과학고는 산책하기 참 힘든 곳이다.

https://www.acmicpc.net/problem/21606

 

21606번: 아침 산책

1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점

www.acmicpc.net


첫 번째 제출

def dfs(start):
    global cnt
    for next in graph[start]:
        if not visited[next]:
            if spot_ls[next-1] == 0:
                visited[next] = True
                dfs(next)
                visited[next] = False
            else:
                cnt += 1


N = int(input())
spot_ls = list(map(int, list(input())))

graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
for i in range(1, N+1):
    if spot_ls[i-1] == 0:
        continue
    visited = [False for _ in range(N+1)]
    visited[i] = True
    dfs(i)

print(cnt)

무지성 dfs를 한 경우

N 크기에 따른 시간초과는 물론, 모든 노드에 간선이 있을 때의 경우에서 시간초과가 난다.

-> 진짜 완전탐색을 했기 때문에 서브태스크2 에서도 시간 초과가 난 것!


두 번째 제출

import sys; sys.setrecursionlimit(int(1e9))


def dfs(start):
    global cnt
    for next in graph[start]:
        if not visited[next]:
            if spot_ls[next-1] == 0:
                visited[next] = True
                dfs(next)
                visited[next] = False
            else:
                cnt += 1


N = int(input())
spot_ls = list(map(int, list(input())))

graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
visited = [False for _ in range(N + 1)]
for i in range(1, N+1):
    if spot_ls[i-1] == 0:
        continue
    visited[i] = True
    dfs(i)

print(cnt * 2)

잔머리를 굴렸다. 어짜피 왔다 갔다는 중복이니까

-> 서브태스크2에 대해서는 성공, 하지만 여전히 시간복잡도는 거의 O(n**2)이기 때문에 터졌다.


세 번째 제출

import sys
sys.setrecursionlimit(int(1e9))


def dfs(start):
    cnt = 0
    visited[start] = True
    for next in graph[start]:
        if not visited[next] and spot_ls[next] == '1':  # 아직 방문 안했고 실내
            cnt += 1
        elif spot_ls[next] == '0':  # 실외인 경우
            cnt += dfs(next)
    return cnt


N = int(input())
spot_ls = '0' + input()
ans = 0

graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

    if spot_ls[u] == '1' and spot_ls[v] == '1':  # 실내에서 실내로 이동 할 경우
        ans += 2


visited = [False for _ in range(N + 1)]
for i in range(1, N+1):
    if spot_ls[i] == '1' or visited[i]:
        continue
    res = dfs(i)
    ans += res * (res-1)

print(ans)

실내를 출발점으로 잡는 것이 아닌 실외를 기준으로 탐색해서 실내의 개수를 찾아 계산한다

-> nP2의 공식을 활용해 순열을 통해 계산하는 방법

접근은 맞았지만 메모리초과로 돌아가지 않는다 왜? 어째서?


네 번째 제출 (바뀐 부분만 첨부)

# 기존 코드
for next in graph[start]:
    if not visited[next] and spot_ls[next] == '1':  # 아직 방문 안했고 실내
        cnt += 1
    elif spot_ls[next] == '0':  # 실외인 경우
        cnt += dfs(next)

# 수정 코드
for next in graph[start]:
    if spot_ls[next] == '1':
        cnt += 1
    elif not visited[next]:
        cnt += dfs(next)

DFS 구문 안에 반복문 조건을 바꿨더니 해결되었다.

기존 : (외부) 재귀

수정 : (외부) 방문한 적 없으면 재귀

 

반복문 조건 때문에 와리가리를 하고 있어서 메모리 초과가 난 것 같다.

그 이외에도 메모리가 빡빡하게 설정되어 있어서 파이파이로는 힘들고

원래 문자열을 정수형을 바꿔서 사용했는데 이것도 메모리를 많이 잡아먹는 것 같다

문자열 인풋의 경우 값을 바꿀 필요가 없다면 그냥 문자열 인덱싱으로 사용하자.

 

 

+

sys.stdin.readline을 안쓰면 채점에 10분이 소요된다.