반응형 BreadthFirstSearch #DFS1 11. 타겟넘버, BFS, 너비우선탐색 * 개인 공부를 위하여 간단하게 정리한 것입니다. * 틀린 부분 지적은 언제나 환영입니다. 지난번 타겟넘버 문제는 DFS를 이용하여 해결하였습니다. 오늘은 BFS를 이용하여 '타겟넘버'를 해결하여 보겠습니다. 이 문제를 BFS로 접근하면 다음과 같이 생각할 수 있습니다. 즉, 첫 번째 numbers의 노드를 기준으로 다음번 노드의 덧셈과 뺄셈한 값을 구하는 방법을 진행합니다. 이렇게 되면 리프노드에는 numbers 노드의 수만큼 덧셈 혹은 뺄셈한 결과가 저장됩니다. 이 리프노드 중에서 target 값과 일치하는 노드의 개수를 구하면 됩니다. 코드는 다음과 같습니다. int solution2(vector numbers, int target) { int ans2 = 0; vector arr_bfs; arr_.. 2021. 9. 13. 이전 1 다음 반응형