์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- ๋ฐฑ์ค #BOJ #1697
- ์ฌ๊ท
- ๋ฐฑ์ค2141
- ์์ข ์ด์๊ฐ์
- ํ๋ก๊ทธ๋๋จธ์ค #๋ฌด์ง์๋จน๋ฐฉ๋ผ์ด๋ธ #C++
- BOJ14719
- 1520๋ด๋ฆฌ๋ง๊ธธ
- html
- github_actions
- boj
- ๋ฐฑํธ๋ํน
- BOJ11729
- ์ด๋ถํ์
- BOJ14501
- ์ํ์ฝ๋ฉ
- BOJ2805
- BOJ1753
- BOJ20444
- BOJ1931
- DP
- BFS
- ๋ฐฑ์ค2533
- BOJ2629
- BOJ11404
- ๋ฐฑ์ค
- BOJ11066
- ๋ฐฑ์ค2110
- BOJ9663
- BOJ2110
- ๋ฐฑ์ค11404
- Today
- Total
poksul_log
[Algorithm] ๋ฐฑํธ๋ํน(Back Tracking) ๋ณธ๋ฌธ
๐๋ฐฑํธ๋ํน์ด๋ ?
ํ์ฌ ์ํ์์ ๊ฐ๋ฅํ ๋ชจ๋ ํ๋ณด๊ตฐ์ ๋ฐ๋ผ ๋ค์ด๊ฐ๋ฉฐ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ
์ฆ, ํด๋ฅผ ์ฐพ์ ๋ ์ค๊ฐ์ ํด๊ฐ ์๋์ด์ ๋งํ ๊ฒฝ์ฐ, ์ด์ ๋จ๊ณ๋ก ๋๋์๊ฐ ํด๋ฅผ ๋ค์ ์ฐพ๋ ๊ธฐ๋ฒ
๐๋ฐฑํธ๋ํน์ ์ฐ์
์ต์ ํ ๋ฐ ์กฐํฉ, ๊ฒฐ์ ๋ฌธ์ ๋ฅผ ํ ๋ ์ฐ์ธ๋ค.
์ฃผ๋ก DFS(๊น์ด ์ฐ์ ํ์)์ ๋ฌถ์ฌ์ ์ ์ฐ์ด๋๋ฐ, DFS๋ ๊ฐ๋ฅํ ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ํ์ํ๋ค.
๋ฐ๋ผ์, n์ด ํฐ ๊ฒฝ์ฐ ๊ฒฝ์ฐ์ ์๋ฅผ ์ค์ฌ์ผ ํ ํ์์ฑ์ด ์๋ค.
→ ์ด ๋ ๋ฐฑํธ๋ํน์ ์ฌ์ฉํ์ฌ ๋ถํ์ํ๊ฑฐ๋ ๋ถ๊ฐ๋ฅํ ๊ฒฝ๋ก๋ฅผ ์ฌ์ ์ ์ฐจ๋จํ๋ ๊ฒ์ ํตํด ๊ฒฝ์ฐ์ ์๋ฅผ ์ค์ผ ์ ์๋ค.
์ฆ, ๊ฐ์ง์น๊ธฐ๋ฅผ ํ ์ ์๋ค๋ ๊ฒ !
โถ DFS์ ์ฐ์ผ ๋ ํ๋ฆ์ ๋ค์๊ณผ ๊ฐ๋ค.
DFS๋ก ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ ๋,
- ์กฐ๊ฑด๋ฌธ์ ๊ฑธ์ด ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ฅผ ์ ์ํ๊ณ ,
- ํด๋น ์ํฉ์ผ ๋ ํ์์ ์ค์ง
- ์ดํ ๊ทธ ์ด์ ์ผ๋ก ๋์๊ฐ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๋๋ก ๊ตฌํ
๋ฐ๋ผ์ ์ด์ ์ผ๋ก ๋์๊ฐ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๋๋ก ๊ตฌํํด์ผ ํ๋ฏ๋ก ๋ฐฑํธ๋ํน์ ์ฌ๊ท์ ํจ๊ป ์ฐ์ธ๋ค.
๐ ๋ํ ์์
๋ฐฑํธ๋ํน์ ๋ํ์ ๋ฌธ์ ๋ก N๊ณผ M ์๋ฆฌ์ฆ๊ฐ ์๋ค.
๋ฌธ์ ๋งํฌ : https://www.acmicpc.net/problem/15649
15649๋ฒ: N๊ณผ M (1)
ํ ์ค์ ํ๋์ฉ ๋ฌธ์ ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์์ด์ ์ถ๋ ฅํ๋ค. ์ค๋ณต๋๋ ์์ด์ ์ฌ๋ฌ ๋ฒ ์ถ๋ ฅํ๋ฉด ์๋๋ฉฐ, ๊ฐ ์์ด์ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํด์ ์ถ๋ ฅํด์ผ ํ๋ค. ์์ด์ ์ฌ์ ์์ผ๋ก ์ฆ๊ฐํ๋ ์์๋ก ์ถ๋ ฅํด
www.acmicpc.net
โถ C++ ์ฝ๋
#include <iostream>
using namespace std;
int n, m;
int arr[9];
bool check[9]; // check[i]์์ i ์ฌ์ฉ ์ฌ๋ถ ์ฒดํฌ์ฉ ๋ฐฐ์ด
void func(int k)
{
if(k == m)
{
for(int i=0; i<m; i++)
cout << arr[i] << ' ';
cout << "\n";
return;
}
for(int i=1; i<=n; i++)
{
if(!check[i])
{
arr[k] = i;
check[k] = 1;
func(k+1);
check[k] = 0;
}
}
}
int main()
{
cin >> n >> m;
func(0);
return 0;
}
func(k+1) ์ดํ k==m ์ธ ์กฐ๊ฑด์ ๋ง์กฑํ์ ๋, return์ ํตํด check[k]=0 ์ด ์คํ๋๋ ์ฌ๊ท ๊ณผ์ ์ด ์ ์ดํด๊ฐ ๋์ง ์์
n=4, m=3์ผ ๋๋ฅผ ์์๋ก ๋ค์ด func(0)๋ถํฐ์ ์ ์ฒด์ ์ธ ํ๋ฆ๋๋ฅผ ๊ทธ๋ ค๋ณด์๋ค.
์ฐ๋์ ํ์ด๋ผ์ดํธ ๋ ๋ถ๋ถ์์,
func(0)๋ถํฐ ์์ํ์ฌ func(3)๊น์ง ์งํํ ๊ฒฝ์ฐ k(3) == m(3) ์ธ base condition์ ๋ง์กฑํ๊ฒ ๋๋ค.
if(k == m)
{
for(int i=0; i<m; i++)
cout << arr[i] << ' ';
cout << "\n";
return;
}
๊ทธ๋ผ ์ ์ฝ๋๋ฅผ ํตํด arr ๋ฐฐ์ด ๋ด์ ์๋ 1 2 3 ์ ์ฐจ๋ก๋ก ์ถ๋ ฅํ๊ฒ ๋๊ณ , return์ด ์คํ๋๋ค.
for(int i=1; i<=n; i++)
{
if(!check[i])
{
arr[k] = i;
check[k] = 1;
func(k+1);
check[k] = 0;
}
}
return ์ดํ func(k+1) ๋ฐ๋ก ์๋ ํ์ธ check[k]=0 ์ ํตํด check[3]์ ๊ฐ์ด 0์ผ๋ก ์ด๊ธฐํ๋๋ค.
๊ทธ๋ผ ์ดํ for๋ฌธ์ ๋ฐ๋ผ 3 ๋ค์์ธ 4(arr[3]=4)์ธ ๊ฒฝ์ฐ, ์ฆ 1 2 4์ ๊ฒฝ์ฐ์ ๋ํด ๊ฒ์ฌํ๊ฒ ๋๋ค.
์ด๋ฌํ ๊ณผ์ ์ ํตํด 1~4 4๊ฐ์ ์ซ์ ์ค 3๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ฅผ ์ ์๋ ๋ชจ๋ ์กฐํฉ์ ๊ฒ์ฌ ๊ฐ๋ฅํ๊ฒ ๋๋ ๊ฒ์ด๋ค.
'Coding Test > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm] ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP) (0) | 2023.07.11 |
---|---|
[Algorithm] ์ ํ ์ ๋ ฌ (0) | 2023.03.20 |