Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
그래프 표현 방식에 대해 질문이 있습니다.
Đã giải quyết
Viết
·
306
2
질문에 앞서, 강사남의 강의로 정말 많이 배우고 있습니다. 감사드립니다.
강의에서는 인접행렬로 그래프를 표현하셨는데, 노드의 갯수가 많이 주어지는 인풋이 있는 경우 시간초과가 났던 경험이 있습니다.
혹시 인접행렬을 사용해서 시간복잡도를 더 줄일 수 있는 방법이 있나요?
그리고 이 강의가 아니더라도 뒤의 강의에서, 인접리스트를 이용한 DFS에 대한 풀이도 포함되어있나요?
python코테 준비 같이 해요!
Quiz
65% người trả lời sai. Hãy thử ngay!
재귀 함수에서 print 문을 재귀 호출 뒤에 두면 출력이 역순으로 되는 이유가 무엇일까요?
전역 변수 충돌 때문에
종료 조건이 없어서
스택에 쌓였다가 역순으로 처리돼서
지역 변수 우선순위 때문에
Câu trả lời 3
1
codingcamp
Người chia sẻ kiến thức
안녕하세요^^
노드 갯수가 많아지면 인접행렬로는 안되고 인접리스트를 써야합니다. 이 강좌에서는 인접리스트로 그래프 탐색을 하는 강의는 없습니다. 이번 경로 탐색 문제를 인접리스트로 짜본것입니다. 아래 코드를 참조해보세요.
def DFS(v):
global cnt
if v==n:
cnt+=1
else:
for nv in g[v]:
if ch[nv]==0:
ch[nv]=1
DFS(nv)
ch[nv]=0
if __name__=="__main__":
n, m=map(int, input().split())
g=[[] for _ in range(n+1)]
ch=[0]*(n+1)
for i in range(m):
a, b=map(int, input().split())
g[a].append(b)
cnt=0
ch[1]=1
DFS(1)
print(cnt)0
0