선생님, 질문이 있습니다.

Question

별 내용은 아닌데 사실

선생님 아이디어와 동일하게 코드 구성을 하였는데요

DFS재귀 매개변수에 string a를 넣는데

다음 트리로 넘어갈 때 저는

DFS(s+1,e,a+='(')

DFS(s,e+1,a+=')')

이렇게 += 연산자를 활용해보았는데요 당연히 구상할 때 부터

문자열을 더해나가야만 종착점에 도달하였을 때 매개변수로 넘어온 a를 출력한다고 생각했는데

그게 아니라 a+'(' a+')'인 이유가 무엇인지 궁금합니다ㅜㅜㅜ

그리고 string 자료형에서 push_back이

파이썬에서의 append와 개념상 동일한 기능을 한다고 봐도 되나요?

감사합니다.

Answer

안녕하세요^^

a+='('와 같이 미리 a의 값을 바꾼 다음 매개변수에 전달하면 재귀함수가 뒤로 백을 했을 때 '('를 추가하지 않은 값으로 되돌아 와야 하는데 백을 해도 '('가 추가된 값 그대로 있습니다.

DFS(s+1, e, res+='(');

cout<<res<<endl;

DFS(s, e+1, res+=')');

위에 코드처럼 짜고n=3을 입력하면 정상적인{ res+'(' } 코드는 (((에 )를 추가해 ((()처럼 진행하지만

위에 코드는 ((((에 )를 추가해 (((()럼 진행할 겁니다. 즉 ((((에서 if(s>n)에 걸려들어 바로 끝나고 뒤로 백을 해 res의 값이 (((으로 되돌아 와야 하는데 되돌아오지 않는 것입니다.

위에 코드처럼 하고 중간위치에서 한 번 출력해보세요. 확인할 수 있을 겁니다.