×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,488,524명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)

백트래킹을 이용하여 다양한 문제를 구현해보자.


모든 문제는 백준 문제를 이용하여 문제를 적용하고 풀어보려 한다.





1. 순열(nPr)


N과 M(1) :: https://www.acmicpc.net/problem/15649

순열은 아래와 같이 코딩 할 수 있다.


현재 값을 넣고 방문을 표시해준 후 다음 재귀를 반복하면 방문된 값들 빼고 계속 처리를 할 수 있다.


그 후 내가 출력 할 값이 m과 같아지면 출력을 하면 된다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc; // 내가 출력할 것
bool visit[10]; // 그 숫자가 쓰는지확인
 
void dfs()
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
 
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (!visit[i])
        {
            visit[i] = true;
            vc.push_back(i);
            dfs();
            vc.pop_back();
            visit[i] = false;
        }
    }
}
 
int main()
{
    scanf("%d %d"&n, &m);
 
    dfs();
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(5) :: https://www.acmicpc.net/problem/15654


인덱스 내로 해결 할 수 없는 값들을 처리하는 방법이다.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int n, m;
int arr[10];
unordered_map<intint> visit;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            if (!visit[arr[i]])
            {
                vc.push_back(arr[i]);
                visit[arr[i]] = 1;
                dfs(i + 1);
                visit[arr[i]] = 0;
                vc.pop_back();
            }
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(9) :: https://www.acmicpc.net/problem/15663


중복된 순열 값을 어떻게 처리할 지 생각해보자.


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<intint> pii;
 
int n, m;
pii arr[10];
 
map<pii, int> visit;
map<vector<int>int> mp;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            if(!visit[arr[i]])
            {
                vc.push_back(arr[i].first);
                visit[arr[i]] = true;
                dfs(i + 1);
                visit[arr[i]] = false;
                vc.pop_back(); 
            }
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d"&val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





2. 조합(nCr)


N과 M(2) :: https://www.acmicpc.net/problem/15650


조합은 이전 수의 참조를 하면 안된다는 것을 생각하면 쉽게 구현 할 수 있다.


재귀에 인자가 들어가는데 현재 인덱스 다음 인덱스를 인자로 보내어 이전 값을 참조 못하도록 하자.


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
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
 
vector<int> vc;
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = cnt; i <= n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(i);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    dfs(1);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(6) :: https://www.acmicpc.net/problem/15655


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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = cnt; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(10) :: https://www.acmicpc.net/problem/15664



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<intint> pii;
 
int n, m;
pii arr[10];
 
map<pii, int> visit;
map<vector<int>int> mp;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = cnt; i < n; i++)
    {
        if (vc.size() < m)
        {
            if(!visit[arr[i]])
            {
                vc.push_back(arr[i].first);
                visit[arr[i]] = true;
                dfs(i + 1);
                visit[arr[i]] = false;
                vc.pop_back(); 
            }
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d"&val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





3. 중복 순열(nπr)


N과 M(3) :: https://www.acmicpc.net/problem/15651


중복 순열은 중복해서 뽑아도 되고 이전 값을 뽑아도 된다는 것을 이용하여 코딩해보자.


위의 내용들을 이해하기 시작했다면 이 코드도 충분히 이해 할 수 있다.



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
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc;
 
void dfs()
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(i);
            dfs();
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    dfs();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





N과 M(7) :: https://www.acmicpc.net/problem/15656



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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





N과 M(10) :: https://www.acmicpc.net/problem/15664



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<intint> pii;
 
int n, m;
pii arr[10];
vector<int> vc;
 
map<vector<int>int> mp;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i].first);
            dfs(i + 1);
            vc.pop_back(); 
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d"&val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





4. 중복 조합(nHr)


N과 M(4) :: https://www.acmicpc.net/problem/15652


중복 조합은 중복 순열에서 이전 값들을 다시 쓸 수 없게만 처리해주면 된다.


이때 중복해서 계속 뽑을 수 있으니 조건에서 간단한 예외처리를 생각해줘보자.


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
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (vc.size() < m && (vc.size() == || vc[vc.size() - 1<= i))
        {
            vc.push_back(i);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    dfs(1);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(8) :: https://www.acmicpc.net/problem/15657



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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m && (!vc.size() || vc[vc.size() - 1<= arr[i]))
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
cs





N과 M(12) :: https://www.acmicpc.net/problem/15666



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<intint> pii;
 
int n, m;
pii arr[10];
vector<int> vc;
 
map<vector<int>int> mp;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m && (!vc.size() || vc[vc.size() - 1<= arr[i].first))
        {
            vc.push_back(arr[i].first);
            dfs(i + 1);
            vc.pop_back(); 
        }
    }
}
int main()
{
    scanf("%d %d"&n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d"&val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus









TIP


조합을 다른 방식으로 한번 이해해보자.


우리는 고등학생 때 조합의 방식을 아래와 같이 생각해본 적이있다.


7개중 4개를 뽑으려면 ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ을 두고 이중에 4군데에만 1을 넣으면 된다고 생각 할 수 있다.


이걸 코드화 시키면 아래와 같다.


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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> vc = { 0,0,0,1,1,1,};
 
    for (int i = 0; i < vc.size(); i++)
        if (vc[i])
            cout << i << " ";
    cout << endl;
 
    while (next_permutation(vc.begin(), vc.end())) {
        for (int i = 0; i < vc.size(); i++)
            if (vc[i])
                cout << i << " ";
 
        cout << endl;
    }
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



  1. rhkddn5161 2018.05.02 23:48

    잘보구 갑니다!

  2. 컴공맨 2018.11.16 21:32

    좋은 글 감사합니다! 질문드리고 싶은것이 있는데, dfs함수의 매개변수로 cnt를 넣는 이유가 뭔가요? 없어도 잘 돌아가던데 혹시 다른 의도를 갖고 코드를 짜신건가해서 여쭤봅니다!

    • 가누 2018.11.16 23:47 신고

      아 의미없는 코드입니다 제가 이전 코드를 이용하여 이 문제를 풀다보니 이런 현상이 나타났네요 죄송합니다

    • 가누 2018.11.16 23:48 신고

      이 글보시는분들중 dfs에서 cnt가 필요한 부분이있고 필요하지 않은 부분이있으니 잘 분간하시면 좋을듯하네요!