인프런 커뮤니티 질문&답변
작성한 질문수
그래프 표현 방식에 대해 질문이 있습니다.
해결된 질문
작성
·
215
2
질문에 앞서, 강사남의 강의로 정말 많이 배우고 있습니다. 감사드립니다.
강의에서는 인접행렬로 그래프를 표현하셨는데, 노드의 갯수가 많이 주어지는 인풋이 있는 경우 시간초과가 났던 경험이 있습니다.
혹시 인접행렬을 사용해서 시간복잡도를 더 줄일 수 있는 방법이 있나요?
그리고 이 강의가 아니더라도 뒤의 강의에서, 인접리스트를 이용한 DFS에 대한 풀이도 포함되어있나요?
답변 3
1
김태원
지식공유자
안녕하세요^^
노드 갯수가 많아지면 인접행렬로는 안되고 인접리스트를 써야합니다. 이 강좌에서는 인접리스트로 그래프 탐색을 하는 강의는 없습니다. 이번 경로 탐색 문제를 인접리스트로 짜본것입니다. 아래 코드를 참조해보세요.
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