DFS를 연습해보자 ==> 일단 go 알고리즘
스택? 재귀?
스택과 재귀: 재귀는 어렵다. 또한 recurison error 위험이 있다. 따라서 가급적 스택을 이용!
큐와 비슷하게 가능.
stack == queue,
pop() == popleft
<동일구조>!!
while stack :
stack.pop()
갈 수 있는 방향 전부 넣어놓고,
위에서 꺼내면, 일단 깊게 들어간다.
방문처리는 큐, 스택에 넣으면서 처리하는게 훨씬 좋다!
백트레킹: 다시 뒤돌아간다.
-
재귀 이용!
-
global 변수 이용 ==> 리턴값을 활용하지 않는다. 단순히 상위 함수로 넘어가는 용도!
-
현재값과 global 변수 비교해서, 가지치기 여부 파악
-
가지치기, 비교를 통해 skip
-
return 현재 함수를 종료하고 자기를 호출 했던 함수로 돌아간다.
-
방문취소 작업
재귀함수: return 재귀 vs 그냥 재귀
그냥 재귀 --> 최종 값이 머든, 활용 못한다. 결국 그 함수가 global 변수를 조작해야함 (함수밖 리스트, 글로벌 변수 등)!
return 재귀 --> 함수가 반환하는 값을 활용가능
