-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
촌수계산질문
23.07.27 21:22 작성 23.07.27 21:23 수정 조회수 202
1
안녕하세요! 선생님이 알리켜주신대로 한번 다시 하다가 저는 bfs 메소드에서 ++count로 했는데 count+1과 무슨 차이가 있을까요?? 백준에서 돌려봤더니 틀렸다고 떠요!
private static void dfs(int start, int count) {
visited[start]=true;
if(start==end){
answer=count;
return;
}
for(int i=1;i<=N;i++){
if(visited[i]==false&&graph[start][i]){
dfs(i,++count);
}
}
}
답변을 작성해보세요.
2
개발자로 취직하기
지식공유자2023.07.28
안녕하세요 :)
++count나 count+1 이나 처음 재귀함수를 호출할 때는 똑같은데요, 그 다음부터는 작성하신 방식의 ++count는 count에 값이 하나씩 누적되고, count + 1에는 값이 누적되지 않기 때문에 동작이 달라집니다!
예를 들어 처음에 idx = 1, cnt = 0으로 들어왔고, 1과 연결된 요소가 2, 3, 4가 있다고 가정했을 때, 우리가 기대하는 건 각각 2, 3, 4를 호출할 때 cnt + 1 인 1이 전달되기를 기대합니다. 그런데 작성하신 방식대로 ++cnt를 하면 2번을 호출할 때는 1이겠지만, 3번을 호출할 때는 2, 4번을 호출할 때는 3 이런 식으로 누적이 되어 동작이 달라질 것 같습니다.
이걸 직접 디버깅 모드로 보고 싶으시다면 위 코드에서 dfs함수를 재귀호출하기 전에 if(idx == 1)이라고 조건문을 걸고, i와 count의 값을 확인하거나 출력해보면 잘 보일 것 같아요!
혹시라도 답변이 명확하지 못했으면 알려주세요! :) 오늘도 공부 화이팅입니다.
답변 1