교대최소제곱법
[백준 파이썬 21606번 아침 산책] 메모리 초과 해결 본문
서울과학고는 산책하기 참 힘든 곳이다.
https://www.acmicpc.net/problem/21606
첫 번째 제출
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분이 소요된다.
'코딩테스트' 카테고리의 다른 글
[백준 파이썬 2294번 동전 2] 메모리 초과 문제 해결 (0) | 2023.10.24 |
---|---|
[백준 파이썬 2617번 구슬 찾기] 재귀함수와 동적계획법 DP (2) | 2023.10.23 |
[백준 파이썬 13334번 철로] heapq의 활용 (2) | 2023.10.17 |
[백준 파이썬 1655번 가운데를 말해요] heapq 사용법 (0) | 2023.10.17 |
[2023 하반기 삼성 코테] 후기 및 분석 (1) | 2023.10.15 |