๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿš“ Self Study/๐Ÿ”“ Programmers

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (ํƒ€๊ฒŸ ๋„˜๋ฒ„, ๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS)) C++

by UKHYUN22 2021. 12. 29.
728x90

 

์•ฝ๊ฐ„ ์Œ.... ์ด๋Ÿฐ ๋ถ„์œ„๊ธฐ์˜ ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค. ๋”ฑ ํ•˜๋‚˜ ์ •๋„ ์ฐจ์ด๋‚˜๋Š” +์™€ - / ์ธ์ ‘ํ•œ ์ฃผ๋ณ€์˜ ๊ฒƒ๋“ค์„ ๋น„๊ตํ•˜๊ณ  ๋“ฑ๋“ฑ

์ด๊ฒŒ ๋ฐ”๋กœ dfs ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ•˜๋ผ๋Š” ๊ฒƒ์ด๋‹ค. ์นด์นด์˜ค ์ปฌ๋Ÿฌ๋ง๋ถ ๋ฌธ์ œ๋ž‘ ๋น„์Šทํ•˜๋‹ค. ๋Š๋‚Œ์„ ์œ ์ง€ํ•˜์ž.

 

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void recur(vector<int> numbers, int target, int sum, int count) {
    
    // count๋„ ๊ณ„์†์ ์œผ๋กœ ์ƒˆ์„œ count๊ฐ€ numbers ๋ฐฐ์—ด์˜ ํฌ๊ธฐ์™€ ๊ฐ™์•„์ง„ ๊ฒฝ์šฐ์—
    // sum ๋˜ํ•œ ์›ํ•˜๋Š” ํ•ฉ target๊ณผ ๋™์ผํ•˜๋‹ค๋ฉด answer๋ฅผ ์ฆ๊ฐ€์‹œํ‚ค๊ณ  return;์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค.
    if(count == numbers.size()) {
        if(sum == target) answer++;
        return;
    }
    
    // ํŒŒ๋ผ๋ฏธํ„ฐ ์ค‘ ํ•˜๋‚˜๋กœ ๋„˜์–ด๊ฐ€๋Š” ๊ฒƒ์ด sum์ด๋‹ค. ํ•˜๋‚˜๋Š” ๋”ํ•˜๊ณ  ํ•˜๋‚˜๋Š” ๋นผ์ค˜์•ผ ํ•œ๋‹ค.
    // ์ฆ‰ numbers์˜ ์ธ์ž๊ฐ€ 5๊ฐœ์ด๋ฉด 2์˜ 5์Šน == 32๊ฐœ์˜ case๋ฅผ ์ „๋ถ€ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ.
    recur(numbers, target, sum+numbers[count], count+1);
    recur(numbers, target, sum-numbers[count], count+1);
}

int solution(vector<int> numbers, int target) {

    // ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ๋‹ค.
    recur(numbers, target, 0, 0);
    return answer;
}