๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.2 : ํƒ€๊ฒŸ ๋„˜๋ฒ„ (DFS)

728x90

๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) : ํƒ€๊ฒŸ ๋„˜๋ฒ„

๋ฌธ์ œ ์ถœ์ฒ˜ - ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ณ ๋“์  Kit

 

๋ฌธ์ œ ์„ค๋ช…

n๊ฐœ์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ •์ˆ˜๋“ค์„ ์ˆœ์„œ๋ฅผ ๋ฐ”๊พธ์ง€ ์•Š๊ณ  ์ ์ ˆํžˆ ๋”ํ•˜๊ฑฐ๋‚˜ ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด [1, 1, 1, 1, 1]๋กœ ์ˆซ์ž 3์„ ๋งŒ๋“ค๋ ค๋ฉด ๋‹ค์Œ ๋‹ค์„ฏ ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์ˆซ์ž๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด numbers, ํƒ€๊ฒŸ ๋„˜๋ฒ„ target์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ ์ˆซ์ž๋ฅผ ์ ์ ˆํžˆ ๋”ํ•˜๊ณ  ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

 

์ œํ•œ์‚ฌํ•ญ
  • ์ฃผ์–ด์ง€๋Š” ์ˆซ์ž์˜ ๊ฐœ์ˆ˜๋Š” 2๊ฐœ ์ด์ƒ 20๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์ˆซ์ž๋Š” 1 ์ด์ƒ 50 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • ํƒ€๊ฒŸ ๋„˜๋ฒ„๋Š” 1 ์ด์ƒ 1000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

 

์ฒ˜์Œ ํ’€์–ด๋ณด๋Š” dfs ์‘์šฉ ๋ฌธ์ œ์ด๋‹ค.

์–ด๋ ต๋‹คใ…ฃ..!!

๊ตฌ๊ธ€์—์„œ ๋‹ค๋ฅธ ์‚ฌ๋žŒ ํ’€์ด ์ฐพ์•„๋ณด๊ณ  ๊ฐ„์‹ ํžˆ ์ดํ•ดํ•ด์„œ ํ’€์—ˆ๋‹ค.

โฌ‡๏ธโฌ‡๏ธโฌ‡๏ธ ์ด๋ถ„ ์„ค๋ช…์ด ์•„์ฃผ ํฐ ๋„์›€์ด ๋˜์—ˆ๋‹ค. ๊ฐ์‚ฌํ•˜๋‹ค

 

https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84C-BFSDFS

 

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํƒ€๊ฒŸ ๋„˜๋ฒ„(BFS,DFS) / C++

โœ… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํƒ€๊ฒŸ ๋„˜๋ฒ„์˜ ์ž์„ธํ•œ ํ’€์ด๋ฒ• - ์žฌ๊ท€์™€ DFS โค๏ธ‍๐Ÿ”ฅ

velog.io

 

 

๋ญ”๊ฐ€ dfs๋กœ ํ’€์–ด์•ผ ๋  ๊ฒƒ ๊ฐ™์€ ๋Š๋‚Œ์€ ๋“ค์—ˆ๋Š”๋ฐ, ํŠธ๋ฆฌ๋ฅผ ๋– ์˜ฌ๋ฆฌ๋Š”๊ฒŒ ์–ด๋ ค์šด ๊ฒƒ ๊ฐ™๋‹คใ…œ

 

 

๋‚˜์˜ ํ’€์ด

#include <string>
#include <vector>
using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int level, int sum){
    if(level == numbers.size()){ // ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์‚ฌ์šฉํ–ˆ์„๋•Œ
        if (sum == target) { // ์ดํ•ฉ์ด target๊ณผ ๊ฐ™๋‹ค๋ฉด
            answer++;
        }
        return;
    }
    dfs(numbers, target, level+1, sum+numbers[level]);
    dfs(numbers, target, level+1, sum-numbers[level]);
}

int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0, 0);
    return answer;
}

 

728x90