글 읽기 - DFS 문제 질문드립니다 ㅠㅠ

1k2k3k4k 1년 전 0

계속 시간 초과가 떠서 어제 질문을 드렸습니다. (답은 올바르게 나옴)

이전엔 if node not in visit: 으로 방문 체크를 했었는데,

시간 복잡도가 O(n)이니 O(1)인 방법을 찾아보라는 조언을 받고

visit 리스트를 0과 1로 체크하는 방식으로 변경하였습니다.

또한 스택을 사용한 방법에서 재귀 함수를 이용한 방식으로 바꾸었습니다.

그런데도 계속해서 시간 초과가 뜹니다.

어느 부분을 수정해야 시간 초과를 막을 수 있을까요?

조언 부탁 드립니다. ㅠㅠㅠ

import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.readline

### Define a graph
V, E, R = map(int, read().split())
graph = [[] for _ in range(V + 1)]

for _ in range(E):
	u, v = map(int, read().split())
	graph[u].append(v)
	graph[v].append(u)

for i in range(V):
	graph[i] = sorted(graph[i])

### Function <DFS>
visit = [0] * len(graph)
stack = list()

def DFS(graph, node):
	visit[node] = 1
	stack.append(node)
	for i in graph[node]:
		if visit[i] == 0:
			DFS(graph, i)

### Main
DFS(graph, R)
for i in range(1, V + 1):
	try:
		print(stack.index(i) + 1)
	except:
		print(0)
	
	
	

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

문제

문제

출처

ICPC

DFS 문제 질문드립니다 ㅠㅠ

1k2k3k4k 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말