Coding Test/Algorithm

[Algorithm] ๋ฐฑํŠธ๋ž˜ํ‚น(Back Tracking)

soyw906 2023. 7. 5. 10:20

๐Ÿ“๋ฐฑํŠธ๋ž˜ํ‚น์ด๋ž€ ?

ํ˜„์žฌ ์ƒํƒœ์—์„œ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ํ›„๋ณด๊ตฐ์„ ๋”ฐ๋ผ ๋“ค์–ด๊ฐ€๋ฉฐ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

์ฆ‰, ํ•ด๋ฅผ ์ฐพ์„ ๋•Œ ์ค‘๊ฐ„์— ํ•ด๊ฐ€ ์•„๋‹ˆ์–ด์„œ ๋ง‰ํž ๊ฒฝ์šฐ, ์ด์ „ ๋‹จ๊ณ„๋กœ ๋˜๋Œ์•„๊ฐ€ ํ•ด๋ฅผ ๋‹ค์‹œ ์ฐพ๋Š” ๊ธฐ๋ฒ•

 

๐Ÿ“๋ฐฑํŠธ๋ž˜ํ‚น์˜ ์“ฐ์ž„

์ตœ์ ํ™” ๋ฐ ์กฐํ•ฉ, ๊ฒฐ์ • ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ์“ฐ์ธ๋‹ค.

์ฃผ๋กœ DFS(๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)์™€ ๋ฌถ์—ฌ์„œ ์ž˜ ์“ฐ์ด๋Š”๋ฐ, DFS๋Š” ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•œ๋‹ค.

๋”ฐ๋ผ์„œ, n์ด ํฐ ๊ฒฝ์šฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ค„์—ฌ์•ผ ํ•  ํ•„์š”์„ฑ์ด ์žˆ๋‹ค.

→ ์ด ๋•Œ ๋ฐฑํŠธ๋ž˜ํ‚น์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ถˆํ•„์š”ํ•˜๊ฑฐ๋‚˜ ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ๋ฅผ ์‚ฌ์ „์— ์ฐจ๋‹จํ•˜๋Š” ๊ฒƒ์„ ํ†ตํ•ด ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ๋‹ค.

 

์ฆ‰, ๊ฐ€์ง€์น˜๊ธฐ๋ฅผ ํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ !

 

โ–ถ  DFS์™€ ์“ฐ์ผ ๋•Œ ํ๋ฆ„์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

DFS๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํƒ์ƒ‰ํ•  ๋•Œ,

  1. ์กฐ๊ฑด๋ฌธ์„ ๊ฑธ์–ด ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ๋ฅผ ์ •์˜ํ•˜๊ณ ,
  2. ํ•ด๋‹น ์ƒํ™ฉ์ผ ๋•Œ ํƒ์ƒ‰์„ ์ค‘์ง€
  3. ์ดํ›„ ๊ทธ ์ด์ „์œผ๋กœ ๋Œ์•„๊ฐ€ ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰ํ•˜๋„๋ก ๊ตฌํ˜„

๋”ฐ๋ผ์„œ ์ด์ „์œผ๋กœ ๋Œ์•„๊ฐ€ ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰ํ•˜๋„๋ก ๊ตฌํ˜„ํ•ด์•ผ ํ•˜๋ฏ€๋กœ ๋ฐฑํŠธ๋ž˜ํ‚น์€ ์žฌ๊ท€์™€ ํ•จ๊ป˜ ์“ฐ์ธ๋‹ค.


๐Ÿ“ ๋Œ€ํ‘œ ์˜ˆ์‹œ

๋ฐฑํŠธ๋ž˜ํ‚น์˜ ๋Œ€ํ‘œ์  ๋ฌธ์ œ๋กœ 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๊ฐœ์˜ ๊ฒฝ์šฐ๋ฅผ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์กฐํ•ฉ์„ ๊ฒ€์‚ฌ ๊ฐ€๋Šฅํ•˜๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.