[๋ฐฑํธ๋ํน] ์ ์ ๋ฐ ํ์ฉ ์์
๐ ๋ฐฑํธ๋ํน์ด๋?
ํด๋ฅผ ์ฐพ๋ ๋์ค ํด๊ฐ ์๋์ด์ ๋งํ๋ฉด ๋๋์๊ฐ์ ๋ค์ ํด๋ฅผ ์ฐพ์๊ฐ๋ ๊ธฐ๋ฒ
→ ์ง๊ธ์ ๊ฒฝ๋ก๊ฐ ํด๊ฐ ๋ ๊ฒ ๊ฐ์ง ์์ผ๋ฉด ๊ทธ ๊ฒฝ๋ก๋ฅผ ๋์ด์ ๊ฐ์ง ์๊ณ ๋๋์๊ฐ๋ค == ๊ฐ์ง์น๊ธฐ
(๊ฐ์ง์น๊ธฐ๋ฅผ ์ผ๋ง๋ ์ํ๋๋์ ๋ฐ๋ผ ํจ์จ์ฑ์ด ๊ฒฐ์ ๋๋ค!)
๋ฐฑํธ๋ํน ๊ธฐ๋ฒ์ ์ ๋ง์ฑ ํ๋จ
์ด๋ค ๊ฐ์ด(์ด๋ค ๋ ธ๋๊ฐ) ํด๊ฐ ๋ ๊ฐ๋ฅ์ฑ์ด ์๋ค๋ฉด ์ ๋งํ๋ค๊ณ ํ๋ฉฐ, ์ ๋งํ์ง ์์ ๊ฐ์ ๊ฐ์ง ์๋ ๊ฒ์ ๊ฐ์ง์น๊ธฐ๋ผ๊ณ ํ๋ค. ์ ๋งํ์ง ์๋ค๊ณ ํ๋จ๋๋ฉด ๊ทธ ๊ฐ์ ์ด์ ์ผ๋ก ๋์๊ฐ ๋ค์ ๊ฐ์ผ๋ก ๋์ด๊ฐ๋ค. (์ด์ ๋ ธ๋๋ก ๋์๊ฐ ๋ค์ ์์ ๋ ธ๋๋ก ๊ฐ๋ค.)
๐ DFS vs ๋ฐฑํธ๋ํน vs ๋ถ๊ธฐํ์ ๋ฒ
DFS | ๊ฐ๋ฅํ ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ๊น์ด ์ฐ์ ์ผ๋ก ํ์ํ๋ ๊ฒ (ํ ๋ฐฉํฅ์ผ๋ก ๊ฐ ์ ์๋ ๊ฒฝ๋ก๋ฅผ ๋จผ์ ํ์) → ํ์ฌ ์ ์ ๊ณผ ์ธ์ ํ ๊ฐ์ ๋ค์ ๋ชจ๋ ๊ฒ์ฌํ์ฌ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ผ๋ก ํฅํ๋ ๊ฐ์ ์ด ์๋ ๊ฒฝ์ฐ ํด๋น ๊ฐ์ ์ ๋ฌด์กฐ๊ฑด ๋ฐ๋ผ๊ฐ๋ ๊ฒ |
'138'์ ํ์ํ ๋ ๋ ๋ฒ์งธ ์ซ์๊ฐ ์ํ๋ ๊ฐ์ด ์๋์๋ ๋ถ๊ตฌํ๊ณ ๋๊น์ง ํ์ ์งํ |
๋ฐฑํธ๋ํน | ํ์ฌ ๊ฐ๋ ๊ธธ์ด ๋ ์ด์์ ํด๊ฐ ์๋๋ผ๊ณ ํ๋จ๋๋ฉด ๋์์ด |
'138'์ ํ์ํ ๋ ๋ ๋ฒ์งธ ์ซ์๊ฐ ์ํ๋ ๊ฐ์ด ์๋๋ฉด ํ์ ์ข ๋ฃ, ๋ค์์ผ๋ก ๋์ด๊ฐ |
๋ถ๊ธฐํ์ ๋ฒ | ์ต์ ํด๋ฅผ ์ฐพ์ ๊ฐ๋ฅ์ฑ์ด ์์ผ๋ฉด ๋ถ๊ธฐํ์ง ์์ → ๋ง์ ์ ๋ง ๋ ธ๋ ์ค ๊ฐ์ฅ ์ข์ ์ ๋ง ๋ ธ๋๋ฅผ ์ ํํ์ฌ ๊ฒฐ์ "์ต์ ์ ํด๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ์ฌ์ฉํ๊ธฐ ์ํ ๋ฐฉ๋ฒ" - ์ ๋งํ๋ค : ํ๊ณ์น๊ฐ ์ด์ ๊น์ง ์ฐพ์ ์ต์ ์ ํด๋ต๋ณด๋ค ๋ ์ข๋ค - ์ ๋งํ์ง ์๋ค : ํ๊ณ์น๊ฐ ์ง๊ธ๊น์ง ์ฐพ์ ์ต์ ์ ํด๋ต๋ณด๋ค ๋ ์ข์ง ์๋ค - ๊ฐ์ง์น๊ธฐ : ์ ๋งํ์ง ์์ผ๋ฉด ๋ ์ด์ ๊ฐ์ง๋ฅผ ๋ป์ด ํ์ํ์ง ์์ * ํ๊ณ์น : ๊ทธ ๋ ธ๋๋ก๋ถํฐ ๊ฐ์ง๋ฅผ ๋ป์ด๋๊ฐ์ ์ป์ ์ ์๋ ํด๋ต์ ํ๊ณ |
bfs, dfs, best-first-search๋ฅผ ์ฌ์ฉํด์ ๊ตฌํํ ์ ์์ง๋ง ์ผ๋ฐ์ ์ผ๋ก best-first-search๋ก ๊ตฌํํ ๊ฒ์ด ๊ฒฐ๊ณผ๊ฐ ์ข๋ค * best-first-search : ๋น์ฉ์ด ๊ฐ์ฅ ์ ์ ๋ ธ๋๋ฅผ ์์ธกํ์ฌ ๊ฐ์ฅ ๋จผ์ ํ์ํ๋ ๊ธฐ๋ฒ์ผ๋ก ๋๋น ์ฐ์ ํ์๊ณผ ๊น์ด ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฅ์ ์ ๊ฒฐํฉํ ๊ฒ → priority queue ์ฌ์ฉ |
๐ ์์
โ N๊ณผ M (1)
https://www.acmicpc.net/problem/15649
1. ํ์ ๊ณผ์ ์์ ๊ฐ์ ๋ด์ int ๋ฐฐ์ด, ๋ฐฉ๋ฌธํ ๋ ธ๋ ์ฒดํฌ๋ฅผ ์ํด boolean ๋ฐฐ์ด(visited) ์์ฑ
2. ์ฌ๊ท๊ฐ ๊น์ด์ง ๋๋ง๋ค cnt๋ฅผ 1์ฉ ์ฆ๊ฐํด์ M๊ณผ ๊ฐ์์ง๋ฉด ๋ ์ด์ ์ฌ๊ท ํธ์ถ X
โ N-Queen
https://www.acmicpc.net/problem/9663
๏ผํธ์ ์ํ์ข์ฐ, ๋๊ฐ์ 4๋ฐฉํฅ์ผ๋ก ๊ฑฐ๋ฆฌ ์ ํ ์์ด ์ด๋ ๊ฐ๋ฅ == ๊ฐ์ ํX, ๊ฐ์ ์ดX, ๋๊ฐ์ X
๏ผ๋ฉ์ธ ํจ์์์ arr[0](0์ด)์ 0~N-1๊น์ง ๋ฃ์ด์ ๊ฐ๊ฐ ํธ ๋ฐฐ์น๊ฐ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ๋๋ก ํจ
1. ์ฒซ๋ฒ์งธ ํธ์ (0,0)์ ๋ฐฐ์นํ์ ๋์ ๊ฒฝ์ฐ์ ์ ๊ณ์ฐ
2. ๋๋ฒ์งธ ํธ์ 0๋ถํฐ ๋ฐฐ์นํ์ฌ ์ด์ ์ ๋ฐฐ์นํ ํธ์ ์์น์ ๋น๊ตํด์ ์กฐ๊ฑด์ ๋ถํฉํ๋์ง ํ์ธ
(์ ๊ทธ๋ฆผ์ ๊ฒฝ์ฐ, ํธ์ ๊ฐ์ ํ์ ๋ฐฐ์นํ ์ ์๊ธฐ ๋๋ฌธ์ return๋จ)
3. ์ฒซ ๋ฒ์งธ ํ(์ธ๋ฑ์ค 0)์ ๋ฐฐ์น๊ฐ ๋ถ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์ ๋ ๋ฒ์งธ ํ(์ธ๋ฑ์ค 1)์ผ๋ก ์ฎ๊ธฐ๊ณ ( → check ํจ์์ ๋ ๋ฒ์งธ for๋ฌธ์ผ๋ก ํํ) ๋ค์ ์ฌ๊ท๋ฅผ ํตํด ์กฐ๊ฑด์ ๋ถํฉํ๋์ง ํ๋ณ
(์ ๊ทธ๋ฆผ์ ๊ฒฝ์ฐ, ํธ์ ๊ฐ์ ๋๊ฐ์ ์ ๋ฐฐ์นํ ์ ์๊ธฐ ๋๋ฌธ์ return๋จ)
4. 1๋ฒ๋ถํฐ 3๋ฒ๊น์ง ๋ฐ๋ณตํด์ ์กฐ๊ฑด์ ๋ง๋ ํธ ๋ฐฐ์น๋ฅผ ์ฐพ๊ณ cnt๊ฐ N-1์ด ๋๋ ์๊ฐ result(๊ฒฝ์ฐ์ ์)๋ฅผ 1 ์ฆ๊ฐ์์ผ์ค๋ค
* ์ ๋ฆฌ
1. ์ฒซ๋ฒ์งธ ์ด(์ธ๋ฑ์ค 0)์ 0~N-1ํ์ ๋ฐฐ์น
for(int i = 0; i<N; i++) { arr[0] = i; check(0); }
2. ํ์ฌ ํธ์ ์์น๊ฐ ์กฐ๊ฑด์ ๋ถํฉํ๋์ง ํ๋ณ
for(int i = 0; i<cnt; i++)
if(arr[i] == arr[cnt] || abs(i-cnt) == abs(arr[i] - arr[cnt])) return;
2-1. ์กฐ๊ฑด X → ํจ์๋ฅผ ์ข ๋ฃํ๊ณ ํธ์ถํ ๊ณณ์ผ๋ก ๋์๊ฐ ํธ์ ์์น๋ฅผ ๋ค์ ํ์ผ๋ก ์ฎ๊ฒจ์ค
2-2. ์กฐ๊ฑด O → ๋ค์ ํธ์ ์์น ํ๋ณ
for(int i = 0; i<N; i++) {
arr[cnt + 1] = i;
check(cnt + 1);
}
3. N-1๊ฐ์ ํธ ๋ฐฐ์น๊ฐ ๋๋๋ฉด result ์ฆ๊ฐ
if(cnt == N - 1) {
result++;
return;
}
โ ๋ถ๋ถ ์์ด์ ํฉ
https://www.acmicpc.net/problem/1182
๐ป ์ฝ๋
#include <iostream>
using namespace std;
int N, S;
int arr[21];
int selected[21];
int result = 0;
void check(int cnt, int sum) {
if (cnt == N) { // ํ๋์ ๊ฒฝ์ฐ์ ์ ์์ฑ
if(S == sum) result++;
return;
}
selected[cnt] = 1;
check(cnt + 1, sum + arr[cnt]);
selected[cnt] = 0;
check(cnt + 1, sum);
}
int main() {
cin >> N >> S;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
check(0, 0);
if (S == 0) cout << result - 1 << '\n';
else cout << result << '\n';
}
* ๋ถ๋ถ ์งํฉ ํ์ฉ
โ ์์ 5๊ฐ ๋ชจ๋ ์ ํ : {-7, -3. -2, 5, 8}
โก ์์ 4๊ฐ ์ ํ (1) : {-7, -3, -2, 5}
โข ์์ 4๊ฐ ์ ํ (2) : {-7, -3, -2, 8}
โ ์ํธ ๋ง๋ค๊ธฐ
https://www.acmicpc.net/problem/1759
๐ป ์ฝ๋
#include <iostream>
#include <algorithm>
using namespace std;
int L, C;
char arr[101];
int selected[101];
void check(int cnt, int start) {
if (cnt == L) {
int con = 0, vo = 0;
string pass = "";
for (int i = 0; i < L; i++) pass += arr[selected[i]];
for (int i = 0; i < pass.length(); i++) {
if (pass[i] == 'a' || pass[i] == 'e' || pass[i] == 'i' || pass[i] == 'o' || pass[i] == 'u') vo++;
else con++;
}
if (vo >= 1 && con >= 2) cout << pass << '\n';
return;
}
for (int i = start; i < C; i++) { // ๋ฌธ์๊ฐ ์ ์ฅ๋ ๊ฐ ์ธ๋ฑ์ค๋ฅผ ์ ํ
selected[cnt] = i;
check(cnt + 1, i + 1);
}
}
int main() {
cin >> L >> C;
for (int i = 0; i < C; i++) cin >> arr[i];
sort(arr, arr + C);
check(0, 0);
return 0;
}
* ์กฐํฉ
โ C๊ฐ์ ๋ฌธ์๋ฅผ ์ ๋ ฅ ๋ฐ๊ณ ์ ๋ ฌ
โก ์๋ก ๋ค๋ฅธ L๊ฐ์ ๋ฌธ์๋ฅผ ์ ํํด์ ์ํธ ๋ง๋ค๊ธฐ
string pass = "";
for (int i = 0; i < L; i++) pass += arr[selected[i]];
์ ํ๋ ์ธ๋ฑ์ค์ ์์นํ ๋ฌธ์๋ฅผ ๊ฐ์ ธ์์ string ๋ฌธ์์ด ์์ฑ
→ pass : acti
โข ์ํธ ์กฐ๊ฑด์ ๋ถํฉํ๋์ง ํ๋ณ
→ ์ต์ ํ ๊ฐ์ ๋ชจ์๊ณผ ์ต์ ๋ ๊ฐ์ ์์์ผ๋ก ๊ตฌ์ฑ
for (int i = 0; i < pass.length(); i++) {
if (pass[i] == 'a' || pass[i] == 'e' || pass[i] == 'i' || pass[i] == 'o' || pass[i] == 'u') vo++;
else con++;
}
if (vo >= 1 && con >= 2) cout << pass << '\n'; // ๊ฐ๋ฅ์ฑ ์๋ ์ํธ ์ถ๋ ฅ
โฃ 2๋ฒ 3๋ฒ์ ๋ฐ๋ณตํ์ฌ ์ ๋ ฅ๋ฐ์ C๊ฐ์ ๋ฌธ์๋ก ๋ง๋ค ์ ์๋ ๋ชจ๋ ์กฐํฉ์ ๋ํด ์ํธ ๊ฐ๋ฅ์ฑ ํ๋ณ