그래프 표현 방식에 대해 질문이 있습니다.
질문에 앞서, 강사남의 강의로 정말 많이 배우고 있습니다. 감사드립니다.
강의에서는 인접행렬로 그래프를 표현하셨는데, 노드의 갯수가 많이 주어지는 인풋이 있는 경우 시간초과가 났던 경험이 있습니다.
혹시 인접행렬을 사용해서 시간복잡도를 더 줄일 수 있는 방법이 있나요?
그리고 이 강의가 아니더라도 뒤의 강의에서, 인접리스트를 이용한 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)기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
0
76
2
스택에서 ')'을 만나는 경우
0
78
3
문제가 어디있나요?
0
64
2
변수 or 함수명
0
61
1
침몰하는 타이타닉 문제 질문입니다
0
56
1
AA.py 책점 에러
0
57
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
160
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
163
2
동적계획법은 사용하는 문제
0
126
2
제 코드 좀 봐주세요
0
148
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
113
0
오류원인?
0
98
0
리스트 선언
0
106
1
침몰하는 타이타닉(그리디) 문제 질문
0
109
1
알고리즘
0
69
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
124
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1