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

1k2k3k4k 1년 전 0

예시는 맞는데 계속 시간 초과가 뜨네요..

어느 부분에서 시간 초과를 줄일 수 있을까요??

조언 부탁드립니다!!

import sys
read = sys.stdin.readline

N, M, R = map(int, read().split())
graph = {}
for i in range(N):
	graph[i + 1] = []

for i in range(M):
	u, v = map(int, read().split())
	graph[u] = graph.get(u, []) + [v]
	graph[v] = graph.get(v, []) + [u]

for i in range(1, N + 1):
	graph[i] = sorted(graph.get(i), reverse = True)



def DFS(graph, R):
	stack = list()
	visit = list()
	stack.append(R)
	
	while stack:
		node = stack.pop()
		if node not in visit:
			visit.append(node)
			stack.extend(graph[node])
	return visit
		
		
		
visit = DFS(graph, R)
for i in range(1, N + 1):
	try:
		print(visit.index(i) + 1)
	except:
		print(0)

jeonggu223 1년 전 0

방문체크를 하는 부분을 리스트로 하셨습니다.

리스트에서 in 연산으로 값이 있는지 체크하는 연산의 시간복잡도는 O(n)입니다.

이를 O(1)로 바꿔보시면 될 것 같네요.

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

문제

문제

출처

ICPC

DFS 문제 질문드립니다!

1k2k3k4k 1년 전 0

jeonggu223 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말