DFS 문제 풀고싶어서 공부하고 있음
언어는 Kotlin인데 로직은 비슷할테니까 언어 달라도 알아봐줄거라 생각함 ㅠ
// values = [1,1,1,1,1], target = 4
class DfsTest(
values : IntArray, target : Int
) {
var answer = 0
var sum = 0
fun dfs(index : Int, ) {
if(index == values.size) {
if(sum == target) {
answer++
}
return
}
dfs(index + 1, sum + values[index+1])
dfs(index + 1, sum - values[index+1])
}
dfs(0,0) // start
}
이거 그 프로그래머스에 타겟찾기였나..그거 풀다 이해 안돼서 그냥 외운건데
values에 +나 -해서 target 값 나올 수 있는 경우의 수 구하는거거든
근데 dfs 재귀함수 안에
dfs(index + 1, sum + values[index+1])
dfs(index + 1, sum - values[index+1])
이렇게 두 번 호출하잖아
근데 로그 보면
dfs(index + 1, sum + values[index+1])
이새끼 다 돌고 나서
dfs(index + 1, sum - values[index+1])
이새끼 도는 것 같거든
재귀 함수 이해가 부족한것 같은데 어떻게 해야 쉽게 이해할 수 있음?
ㅇㅇ 맞는디
동기적이니까용 ㅇㅅㅇ - dc App
이해가 잘 안되는게 dfs(index + 1, sum + values[index+1]) 얘 돌아서 밑에꺼가 실행되지 않고 위로 올라가잖아 근데 if(index == values.size)이거로 return 되어버리면 dfs(index + 1, sum - values[index+1]) 이새낀 실행될 기회가 없는거 아니야? 진짜 빡대가리같은 질문 해서 미안해 ㅠㅠㅠ
재귀함수 호출이잖아 그럼 마지막줄까지 돌고나면 호출됐던위치로 돌아오지? 그게 여전히 dfs함수안쪽이라 다음함수가 실행됨
코틀린 모르겠네 ㅇㅅㅇ 변수 선언 안 하고 바로 박으면 0부터 시작임 ㅇㅅㅇ? - dc App
dfs`1 함수 안에서 dfs 함수를 다시 호출함(플러스, 마이너스 총 2번) 그럼 이 둘을 dfs`2(+), dfs`2(-) 라고 한다면. dfs`2(+) 끝나고나서 dfs`2(-)가 호출되고 dfs`1함수가 종료됨