back tracking에서 여러 경우의수를 dfs로 탐험해야 할때,

state → state로 가는 것과 다르게

하나의 state에서 다른 여러 state들로 가야한다. 이때 그 전 state를 기억하고 있어야 back tracking을 했을때 그 상태 그대로 존재한다.

머릿속 논리의 흐름이 어떻게 되어야 하는가?

<aside> 💡 언제 dfs를 써야 하는가? solution(){

//상어가 물고기를 먹는다

//물고기가 이동한다

//상어가 이동한다

//상어가 물고기를 먹는다

//반복

}

</aside>

위의 흐름대로 생각할수 있다. 여기서 상어가 이동할때 back-tracking문제인만큼 (사실 그냥 dfs임) 상어가 이동할때는 dfs를 써야한다 (bfs써도 큰 상관 없을듯) 어차피 파고 들어가서 max값만 확인하고 나오는 것이기때문에

위에서 solution이 아래와 같이 dfs가 들어가는 순간

<aside> 💡 언제 dfs를 써야 하는가? solution(){

//상어가 물고기를 먹는다

//물고기가 이동한다

//상어가 이동한다 dfs();

//상어가 물고기를 먹는다

//반복

}

</aside>

ㅇ 아래와 같이 구조가 바뀐다 recursive한 구조로 초기에 물고기만 먹고 (생각의 흐름이 자연슬버게 되도록 조금 더 생각해보자.

<aside> 💡 언제 dfs를 써야 하는가? solution(){

//상어가 물고기를 먹는다 (초기조건)

dfs();

}

dfs(){

//상어가 물고기를 먹는다

//물고기가 이동한다

//상어가 이동한다 dfs();

}

</aside>