-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
else문 내를 다르게했더니 출력이 이상합니다.
20.06.03 02:26 작성 조회수 147
1
path[L] = +a[L];
s += a[L];
DFS(L + 1, s);
path[L] -= a[L];
s -= a[L];
DFS(L + 1, s);
path[L] = 0;
DFS(L+1, s);
dfs함수의 else문 내를 이렇게 s를 따로 계산하고 s를 넘겨주니, 2460이 두번 출력됩니다.
선생님 코드와의 차이는 s-a[L]을 넘겨줬느냐 계산후 넘겨줬느냐 인데 어떤 차이 때문인가요?
답변을 작성해보세요.
1
김태원
지식공유자2020.06.03
else{
s=s+a[L];
DFS(L+1, s);
s=s-a[L]
DFS(L+1, s);
DFS(L+1, s);
}위의 코드를 가지고,
영상에서 처럼 처음 DFS(1, 0)으로 시작해서 2+4+6 까지 s에 더하고 8을 적용하는 함수인 DFS(4, 12) 함수를 가지고 설명하겠습니다.
s=s+a[L]; //s=12+8이 되어 매개변수 s=20이 됩니다.
DFS(L+1, s); //DFS(5, 20)으로 호출이 일어납니다.
s=s-a[L]; // s=20-8이 되어 s=12가 됩니다. 여기서 중요한게 되돌아 왔을 때 매개변수 s의 값은 20입니다. 위 코드 s=s+a[L]에서 DFS(4, 12)의 매개변수 s를 20으로 바꾸었다는 것을 명심하세요. 즉 이 코드는 s=s+a[L]에서 8을 더한 것을 다시 8을 빼주어 원래 s값인 12로 되돌리는 효과입니다.
DFS(L+1, s); //DFS(5, 12) 가 호출되어 2+4+6-8인 상황인데 s는 4가 아니라 12로 넘어간다는 것이 오류입니다.
DFS(L+1, s); //DFS(5, 12)가 호출됩니다. 2+4+6 상황으로 여기는 맞는 경우입니다. 여기가 맞을 수 있는 것은 s=s-a[L]에서 원래의 s값이 12로 바꾸어 놓았기 때문입니다.
결론은 DFS(4, 12)의 매개변수인 s를 함수 안에서 바꾸면 안되는 것입니다. 함수 안에서는 계속 12를 유지해야 합니다.
스스로 상태트리를 그려가면서 집요하게 분석해 보세요.
0
답변 2