알고리즘 문제 풀이 check : DFS유형.

이 글은 개인적인 공부를 위해 쓴 글로, 가독성이 좋지 않습니다.

DFS유형에 대한 배경 소개는 생략한다.

 

 

재귀함수, stack을 이용하는것.

4개 혹은 몇개의 선택지 중에 1개를 고르고, 

다음 단계에서 반복해서(재귀) 1개를 고른다.

더이상 갈수없을 때에는 부모노드로 되돌아간다.

 

부모 노드로 되돌아가는 경우는 언제인가?

1. 막다른길 : 더이상 경우가 없을 때(최대 깊이를 구하는 문제라면 최대 깊이를 저장하고..)

2. 목표를 달성했을 경우(최대 깊이가 N인 경우, N에 도달했을때 Good Case로 처리하고..)

* 막다른 길은 for문을 돌때, 모든 케이스가 조건 불가 하면된다.

 

부모 노드로 되돌아갈 때 해야할 일은?

현재 dfs함수로 들어오기 전 상태로 만들어야 한다.(undo라고 기억한다)

* stack에 변수를 push했으면 다시 pop하고

* visited 배열이 있다면 visit하지 않은 상태로 만든다.

 

부모 노드로 되돌아가면, 그 다음 선택지를 탐색을 계속할수 있는 흐름인지 체크한다.

Good Case인 경우

for문 안에서 good case를 판별했다면, 함수를 나가지 말고 for문을 계속 돌아야 한다.

(for문으로 가는게 곧 부모 노드로 되돌아가는것이다.)

그렇게 안하려면, Good Case판별을 for문 안에서 하지 말자. 

 

이번에 만든 코드의 경우  good case끝에 continue가 있는걸 볼수있다.

 

선택지 고르기

if (선택 가능한 조건 = Wall이 아닌지, 0으로 나누지 않는지 같은것. ) 

조건을 충족하면 dfs( ... ) 를 가자.

 

 

 

 

고려해야 할 일들

 

<중요1> Undo : 부모 노드로 되돌아가야 한다는 것이다.

stack이 필요한 이유는 재귀함수가 

stack에 넣을 변수라면, dfs()함수의 인자로 넘겨줄 수도 있다.

 

그런데 <stack> 대신 <vector>를 써도 속도는 비슷한것같다.

 

 

<중요2> 재귀함수가 실행되는 동안 누적 계산되는 값이 있다.

이 값을 저장할 전역변수가 있거나, 재귀함수의 인자로 넘겨준다.

위 코드에서 result에 해당함.

 

<중요3> 최초 값을 잘 확인 / 재귀를 그만할 때를 잘확인한다.

재귀를 그만하는 조건은 언제인가?

Good Case 혹은 더이상 탐색할 게 없을때. 

 

<중요4> 매 케이스마다 초기화 해준다.

매 케이스마다 초기화 할 값을 잘 초기화 해준다

dfs를 갈때마다 초기화 해야하는 경우도 있다.

넘겨주는 값과 초기화 하는 값 구분...

 

 

---------------------------------------------------------------------

 

입력으로 
N개의 숫자를 받아 Num[ 20 ]에 저장한다.
op의 갯수 op[4]에 저장한다.

selected[20]에는 지금까지 선택한 op를 저장한다.

<재귀 함수가 하는 일>
op를 4가지 중에서 선택하고, 
숫자를 계산한다.

지금까지 계산한 결과 result 와, 몇 번째 계산인지 알아야 한다. 

 

선택하면 안되는값(이미 선택한 값, 특이한값-0으로나누는값) 을 알아야한다.

그러기 위해서 op갯수를 업데이트 해줘야 함.

 

* 숫자 N개를 다 썼으면...
더이상 재귀하지 않고  Good Case 처리팀에 맡긴다(누적계산값을 처리한다)

그다음 부모 노드로 되돌아가 탐색을 게속한다.

 

굿케이스 조건.
숫자가 N개라면 op는 N-1개만 선택하면 된다.
그러므로 N-1번째이면 
더이상 깊게 가지 않는다.
Good Case로 간주한다.


op를 4개중에서 선택한다.
count 를 1증가 (dep으로 이름변경)
selected[n] = 지금까지 선택한 op
>> sel[n]이라고 하자.  >>opST 스택으로변경.

n=0부터 시작이다.

첫번째 재귀 실행은... 
count 는 0에서 1이 된다.
Num[0] op(+) Num[1]

n번째 계산이라면
Num[n] sel[0] Num[n+1]
(n+1이 N-1이 될때까지 실행하니까
n이 N-2 될때까지 실행하면된다.
총 N-1번 실행)


부모 노드로 돌아가기
: Good Case가 되었거나
 더이상 고를게 없거나
 0으로 나누기를 골랐거나.

sel[마지막] 값을 제거한다.
result 계산을 되돌린다.
count 를 1 내린다.

selected 스택을 만들자 
result 스택을 만들자.
op[4]에 있는 값을 더한다.





부모 노드로 되돌아가기 위해서 필요한것.
이경우는 
일단 재귀하는동안 계산결과 C를 저장해야 한다.


최대값, 최소값을 저장해야 한다.