zhoang3   7년 전

인접배열로 작성해 봤는데

혹시 코드가 잘못된건지

리스트로 짜야하는지 알려주세요....

chogahui05   7년 전

간단하게 반례 투척해 보겠습니다.

5 5 2

1 2

2 3

2 4

3 5

4 5


zho님 프로그램으로 직접 돌려보세요. 어떻게 결과가 나오는지.

chogahui05   7년 전

일단 dfs는 return문 위치가 문제인데.

깊이 우선 탐색은 어떻게 수행하나요? 최대한의 깊이까지 들어가보고, 더 이상 갈 수 없다면 백 트래킹으로 빠져나오지요.

다른 길이 있으면, 그 길로 들어가 보고요.


a와 b, c가 인접해 있습니다. 님 코드상으로는 a를 방문한 후에, b를 방문해 봅니다. 그리고 좌르륵 방문한 후에

다시 a로 돌아옵니다. 그 다음에 c가 인접해 있음에도 불구하고 c를 방문하지 않죠.


다음에 bfs.

back() 함수로 큐의 맨 뒤에 있는 것을 불러오는군요. 이건 최근에 추가된 원소이지요.

그러면 어떤 일이 벌어지느냐. 아래 데이터를 넣었을 때


(1) 큐에 1이 넣어집니다. 그리고 1을 출력하겠죠? 그리고 빠지겠군요.

(2) 큐에 2, 3, 4가 차례로 넣어집니다. 그러면, 이것들이 차례대로 출력되겠네요.

(3) 그리고, back 함수에 의해서 4와 인접한 것들이 넣어질 거고..


아무튼 그러겠네요. 실제로는 큐에 넣는 연산 자체가 처음에 없었기 때문에, 처음에 큐는 비어 있는 상태로 있을 거고

push 연산이 수행되지도 않겠지만.

chogahui05   7년 전

인접 리스트로 짜면 빨라질 수 있습니다만. 어디까지나

전체 노드 갯수 대비, 전체  path 갯수가 무지하게 작을 때나 효과를 보는 것이지 그 외의 경우에는 효과 없습니다.

요새 c++을 이용해서 코딩들을 많이 하시더라고요.


물론, 저는 힙이나, 트리 같은 건 c언어로 직접 구현한 걸 써 왔지만, 여기 와서는 그냥 c++ STL을 씁니다. 

가져오기 귀찮은 것도 있고요.. 그렇더라고요.


java의 자료 구조 뭐라 하지? java.util에 있나요? (HashMap, ArrayList, ...)

이거나 c++ STL이나. 많이들 물어보시더라고요.


다른 것은 모르겠습니다만..

(1) 이 함수가 어떤 일을 하는지. 성능은 어떻게 되는지.

(2) 이 자료구조는 어떤 특성을 가지는지.


이 둘은 정확하게 짚고 넘어가세요. 푸신 문제들을 보니, 기본적인 자료구조는 어느 정도 아시는 거 같으시더라고요.

(1)은 확실하게 짚고 넘어가실 필요가 있어요. 생각보다 많이 간과하고 넘어가십니다.

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