(그림판 발퀄 ㅈㅅ)
백준 1260번 풀고있는데
DFS 알고리즘이
시작정점 v 방문후 push
while(Stack is not empty){
방문하지않은 인접정점 w가 존재시 방문후 push
존재하지 않을시 pop
}
이거잖아
근데 위에같은 그래프는 1-2-7 타면 스택에 1,2,7쌓이는데 pop하면서 1로 돌아오면 스택이 비게되잖아
이걸 어떻게 해결해야 좋을까... 알고리즘 수정해야될거같은데 어떻게 건드려야될지 모르겠음..
재귀는 가급적이면 쓰고싶지 않음...
백준 1260번 풀고있는데
DFS 알고리즘이
시작정점 v 방문후 push
while(Stack is not empty){
방문하지않은 인접정점 w가 존재시 방문후 push
존재하지 않을시 pop
}
이거잖아
근데 위에같은 그래프는 1-2-7 타면 스택에 1,2,7쌓이는데 pop하면서 1로 돌아오면 스택이 비게되잖아
이걸 어떻게 해결해야 좋을까... 알고리즘 수정해야될거같은데 어떻게 건드려야될지 모르겠음..
재귀는 가급적이면 쓰고싶지 않음...
1에서 스택이 왜 빔?
ㄴ while 진입 전 1 방문 1 삽입 진입 후 인접노드 탐색 - 2 방문후 push, 두번째루프 - 인접노드 탐색 - 7방문후 push, 세번째루프 - 인접노드 없으므로 pop, 현위치 7 네번째루프 - 인접노드 없으므로 pop, 현위치 2, 다섯번째루프 - 인접노드 없으므로 pop, 현위치 1, 6번째 루프 stack이 empty이므로 탈출
이렇게되던데
코드 긁어서 올려바
ㄴ
https://ideone.com/DTDBPE
이거 링크 들어가심되여
https://ideone.com/p6zFVL
while에서 인접노드 순회 안하고 하나만 들어가서 그런거같음 그거 고쳐봄
엥? 인접노드 다넣는거였음??;;
방문하고 그 자리 그냥 스택에 넣는줄알았는데 인접 다넣고 빼면서 움직이는거였구나.... ㄱㅅㄱㅅ 배워갑니다 for문도 신기하게 쓰시넹
인접노드는 다넣어야지
아 근데 이렇게하면 스택에 오름차순으로 들어가서 dfs가 내림차순으로 진행되네... 이건 좀 고민해봐야될듯
ㄴ 몰랏슴 ㅋㅋ
스택에 반대로 넣어라
2,3,4 가 아니라 4,3,2 순서로 넣어라
ㄴ 와 역순으로 넣으니까 되넹;; ㄱㅅㄱㅅ
님들 개똑똑하네여 ㄷㄷ
단순한 문제는 이렇게 풀리지만, 복잡한건 dinic 할때처럼 현재 몇번까지 봤는지 저장하면서 해야함
ㄷㄷ