[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๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ฅผ ์ ์๋ ๋ชจ๋ ์กฐํฉ์ ๊ฒ์ฌ ๊ฐ๋ฅํ๊ฒ ๋๋ ๊ฒ์ด๋ค.