๊น์ด/๋๋น ์ฐ์ ํ์(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 ์์ฉ ๋ฌธ์ ์ด๋ค.
์ด๋ ต๋คใ ฃ..!!
๊ตฌ๊ธ์์ ๋ค๋ฅธ ์ฌ๋ ํ์ด ์ฐพ์๋ณด๊ณ ๊ฐ์ ํ ์ดํดํด์ ํ์๋ค.
โฌ๏ธโฌ๏ธโฌ๏ธ ์ด๋ถ ์ค๋ช ์ด ์์ฃผ ํฐ ๋์์ด ๋์๋ค. ๊ฐ์ฌํ๋ค
๋ญ๊ฐ 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;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/PGS] Lv.3 : ๋ฑ๊ตฃ๊ธธ (DP) (1) | 2023.02.23 |
---|---|
[C++/PGS] Lv.3 : ๋คํธ์ํฌ (DFS/BFS) (0) | 2023.02.23 |
[C++/PGS] Lv.2 : ๊ฒ์ ๋งต ์ต๋จ๊ฑฐ๋ฆฌ (BFS) (0) | 2023.02.23 |
[PGS] Lv.0 (์ฝ๋ฉํ ์คํธ ์ ๋ฌธ) 12์ผ์ฐจ ๋ฌธ์ (0) | 2023.02.20 |
[PGS] Lv.0 (์ฝ๋ฉํ ์คํธ ์ ๋ฌธ) 11์ผ์ฐจ ๋ฌธ์ (0) | 2023.02.20 |