Inflearn コミュニティ Q&A
投稿した質問数
그래프 표현 방식에 대해 질문이 있습니다.
解決済みの質問
作成
·
298
2
질문에 앞서, 강사남의 강의로 정말 많이 배우고 있습니다. 감사드립니다.
강의에서는 인접행렬로 그래프를 표현하셨는데, 노드의 갯수가 많이 주어지는 인풋이 있는 경우 시간초과가 났던 경험이 있습니다.
혹시 인접행렬을 사용해서 시간복잡도를 더 줄일 수 있는 방법이 있나요?
그리고 이 강의가 아니더라도 뒤의 강의에서, 인접리스트를 이용한 DFS에 대한 풀이도 포함되어있나요?
python코테 준비 같이 해요!
回答 3
1
codingcamp
インストラクター
안녕하세요^^
노드 갯수가 많아지면 인접행렬로는 안되고 인접리스트를 써야합니다. 이 강좌에서는 인접리스트로 그래프 탐색을 하는 강의는 없습니다. 이번 경로 탐색 문제를 인접리스트로 짜본것입니다. 아래 코드를 참조해보세요.
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