백트래킹
백트래킹
백트래킹은 “가능한 모든 해”를 탐색하는 과정에서, 불필요한 경로를 미리 차단하고, 유효하지 않은 경로는 되돌려서 다른 경로를 탐색하는 알고리즘
📌 1. 1부터 N까지에서 골라 길이가 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
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAX (8+1)
int N, M;
int seq[9];
bool visited[9];
void backtrack(int index) {
if (index == M) { //M개 수 다 선택하면 출력
for (int i = 0;i < M;i++) {
printf("%d ", seq[i]);
}
printf("\n");
return;
}
for (int i = 1;i <= N;i++) { //1부터 N까지
if (!visited[i]) {
visited[i] = 1; //방문 표시
seq[index] = i; //배열에 추가
backtrack(index + 1);
visited[i] = 0; //방문 되돌리기
}
}
}
int main() {
scanf("%d %d", &N, &M);
backtrack(0); //index는 0부터
return 0;
}
/*
1~N 자연수 중에서 중복 없이 길이가 M인 수열을 모두 구하라
*/
📌 2. 스도쿠
코드 보기
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<stdio.h>
#define MAX (9+1)
int board[MAX][MAX];
int issafe(int row, int col, int val) {
for (int i = 0; i < 9; i++) { //가로 세로 유효여부 확인
if (board[row][i] == val || board[i][col] == val) {
return 0;
}
}
int start_row = row - row % 3;
int start_col = col - col % 3;
/*
if (row % 3 == 0) start_row = row;
else if (row % 3 == 1) start_row = row - 1;
else if (row % 3 == 2) start_row = row - 2;
if (col % 3 == 0) start_row = col;
else if (col % 3 == 1) start_col = col - 1;
else if (col % 3 == 2) start_col = col - 2;
*/
for (int i = start_row; i < start_row + 3; i++) { //3x3 유효여부 확인
for (int j = start_col; j < start_col + 3; j++) {
if (board[i][j] == val) {
return 0;
}
}
}
return 1;
}
void print() {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
printf("%d ", board[j][k]);
}
printf("\n");
}
}
int beReturn() { //모든 칸 다 채웠는지 확인
int ret = 1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) ret = 0;
}
}
return ret;
}
int ret_flag = 0;
void solve() {
if (ret_flag) return;
if (beReturn()) { //원하는 목표 도달시 return flag = 1;
ret_flag = 1;
return;
}
//빈곳 찾기
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) { //col
if (board[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
if (issafe(i, j, k)) {
board[i][j] = k;
solve();
if(!ret_flag) board[i][j] = 0; //원하는 목표 도달 못하면 다시 되돌리기
}
//
}
return;
}
}
}
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%d", &board[i][j]);
}
}
solve();
if (ret_flag) {
print();
}
return 0;
}
📌 3. 수열의 합 특정 값인 부분 수열의 개수
코드 보기
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
#include<stdio.h>
#define MAX (20+1)
int N, S;
int num[MAX];
int cnt = 0;
void solve(int index, int sum, int num_cnt) {
/*
index : num배열에서 선택/미선택할 원소 인덱스
sum : 현재 분기까지의 합
num_cnt : 선택한 원소의 개수(문제 조건 : 양수여야 함)
*/
if (index == N) {
if (sum == S && num_cnt > 0) cnt++;
return;
}
//1. 포함
solve(index + 1, sum + num[index], num_cnt + 1);
//2. 미포함
solve(index + 1, sum, num_cnt);
}
int main() {
scanf("%d %d", &N, &S);
for (int i = 0;i < N;i++) {
scanf("%d", &num[i]);
}
solve(0, 0, 0);
printf("%d\n", cnt);
return 0;
}
/*
요구사항 : 부분수열의 합이 S인 경우의 수
-> 부분 수열을 선택
1. 현재 원소를 포함하는 경우
2. 포함 안하는 경우
*/
📌 4. N과 M(2)
코드 보기
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
#include<stdio.h>
#define MAX (8+1)
int N, M;
int ans[MAX];
int issafe(int num) {
for (int i = 0;i < M;i++) {
if (ans[i] == num) return 0;
}
return 1;
}
void solve(int selectNum, int selectCnt) {
if (selectCnt == M) {
for (int i = 0;i < M;i++) {
printf("%d ", ans[i]);
}
printf("\n");
return;
}
for (int i = selectNum;i <= N;i++) {
if (issafe(i)) {
ans[selectCnt] = i;
solve(i, selectCnt + 1);
ans[selectCnt] = 0; //다른 곳에서 탐색할 때 유효하지 않은 index에서 걸리지 않도록
}
}
}
int main() {
scanf("%d %d", &N, &M);
solve(1, 0);
return 0;
}
/*
1~N에서 중복 없이 M개를 골라라
1. 일단 차례대로 골라서 저장, 출력
2. 하나 빠꾸 저장 수정, 출력
...
*/
조금 변형 코드 보기
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
#include<stdio.h>
#define MAX (8+1)
int N, M;
int ans[MAX];
int issafe(int num, int selectCnt) {
for (int i = 0;i < selectCnt;i++) {
if (ans[i] == num) return 0;
}
return 1;
}
void solve(int selectNum, int selectCnt) {
if (selectCnt == M) {
for (int i = 0;i < M;i++) {
printf("%d ", ans[i]);
}
printf("\n");
return;
}
for (int i = selectNum;i <= N;i++) {
if (issafe(i, selectCnt)) {
ans[selectCnt] = i;
solve(i, selectCnt + 1);
//ans[selectCnt] = 0; //다른 곳에서 탐색할 때 유효하지 않은 index에서 걸리지 않도록
}
}
}
int main() {
scanf("%d %d", &N, &M);
solve(1, 0);
return 0;
}
/*
1~N에서 중복 없이 M개를 골라라
1. 일단 차례대로 골라서 저장, 출력
2. 하나 빠꾸 저장 수정, 출력
...
*/
📌 5. N과 M(3)
코드 보기
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
#include<stdio.h>
#define MAX (7+1)
int N, M;
int ans[MAX];
void solve(int numCnt, int num) { //numCnt : 개수
if (numCnt == M) {
//ans배열 출력
for (int i = 0; i < M; i++) {
printf("%d ", ans[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= N; i++) {
ans[numCnt] = i;
solve(numCnt + 1, i);
//ans[numCnt] = 0;
}
}
int main() {
scanf("%d %d", &N, &M);
solve(0, 0);
return 0;
}
/*
1부터 N까지 자연수 중에 M개를 고른 부분 수열, 중복 가능
1. 선택, 분기
2. 다뽑으면 출력, 리턴
3. 되돌리기
*/
📌 6. N과 M(4)
첫 코드 보기
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
#include<stdio.h>
#define MAX_ANS 8
int ans[MAX_ANS + 1] = { 0 }; //index 1부터 8 사용
void solve(int N, int M, int step) {
if (step == M + 1) {
for (int i = 1;i <= M;i++) printf("%d ", ans[i]);
printf("\n");
return;
}
for (int i = 1;i <= N;i++) {
if (i >= ans[step - 1]) {
ans[step] = i;
solve(N, M, step + 1);
}
}
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
solve(N, M, 1);
return 0;
}
/*
문제의 조건에 만족하는 수열 출력
중복 수열 여러번 출력 금지
공백으로 구분 수열
사전순 증가하는 순서로 출력
조건
1. 1~N 자연수 중 M개 고른 수열
2. 수 중복 가능
3. 비내림차순
#1)
3 1
1 2 3 중 1개를 고른 수열
1
2
3
*/
조금 개선 코드 보기
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
#include<stdio.h>
#define MAX_ANS 8
int ans[MAX_ANS + 1] = { 0 }; //index 1부터 8 사용
void solve(int N, int M, int step, int cur_val) {
if (step == M + 1) {
for (int i = 1;i <= M;i++) printf("%d ", ans[i]);
printf("\n");
return;
}
for (int i = cur_val;i <= N;i++) { //현재 추가값 이상만 추가
ans[step] = i;
solve(N, M, step + 1, i);
}
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
solve(N, M, 1, 1); //step 1, cur_val 1부터 시작
return 0;
}
📌 7. N과 M(5)
코드 보기
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
#include<stdio.h>
#include<stdlib.h>
#define MAX_ANS 8
int N, M;
int inputArr[MAX_ANS] = {0}; //입력 배열
int visited[MAX_ANS] = { 0 }; //입력의 방문 확인 배열
int ans[MAX_ANS + 1] = { 0 }; //답 출력할 배열
void solve(int step, int input_index) {
if (step == M + 1) {
for (int i = 0;i < M;i++) {
printf("%d ", ans[i]);
}
printf("\n");
return;
}
for (int i = 0;i < N;i++) {
if (!visited[i]) {
visited[i] = 1;
ans[step - 1] = inputArr[i];
solve(step + 1, i);
visited[i] = 0; //사용한건 다시 0으로 돌려놔야 다음번에 반영 안됨
}
}
}
int cmp(const void* a, const void* b) {
return *((int*)a) - *((int*)b);
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0;i < N;i++) {
scanf("%d", &inputArr[i]);
}
qsort(inputArr, N, sizeof(int), cmp);
solve(1); //step 1 부터 시작
return 0;
}
/*
N개의 자연수 중에서 M개를 고른 수열
*/
📌 8. 치킨 배달
코드 보기
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#define INF (~(1<<31))
#define MAX_MAP 50
#define MAX_CHICKEN 13
#define MAX_HOME (MAX_MAP * 2)
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
typedef struct {
int x;
int y;
}Pos;
enum Map {
EMPTY = 0,
HOME = 1,
CHICKEN = 2,
};
int map[MAX_MAP][MAX_MAP] = { 0 };
Pos stack_chicken[MAX_CHICKEN];
int top_stack_chicken = 0;
Pos stack_home[MAX_HOME];
int top_stack_home = 0;
int N, M;
int selected[MAX_CHICKEN] = { 0 };
int min_tot_dist = INF;
int get_distance(int home, int chicken) {
Pos h = stack_home[home];
Pos c = stack_chicken[selected[chicken]];
int x = MAX(h.x, c.x) - MIN(h.x, c.x);
int y = MAX(h.y, c.y) - MIN(h.y, c.y);
return x + y;
}
void cal_distance() {
int tot_dist = 0;
for (int i = 0;i < top_stack_home;i++) {
int min_dist = INF;
for (int j = 0;j < M;j++) {
int cur_dist = get_distance(i, j);
if (cur_dist < min_dist) min_dist = cur_dist;
//printf("%d\n", cur_dist);
}
tot_dist += min_dist;
//printf("%d\n", tot_dist);
}
if (tot_dist < min_tot_dist) min_tot_dist = tot_dist;
}
void select_chicken(int cur, int cnt) { // 치킨 조합 생성
if (cnt == M) {
cal_distance();
return;
}
for (int i = cur;i < top_stack_chicken;i++) {
selected[cnt] = i;
select_chicken(i + 1, cnt + 1);
}
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == HOME) {
stack_home[top_stack_home++] = (Pos){ i,j };
}
else if (map[i][j] == CHICKEN) {
stack_chicken[top_stack_chicken++] = (Pos){ i,j };
}
}
}
select_chicken(0, 0);
printf("%d\n", min_tot_dist);
return 0;
}
/*
폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값 구하라
r과 c는 1부터 시작한다.
치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리
도시의 치킨 거리 = 모든 집의 치킨 거리의 총합
수익 많이 치킨집 수 최대 M개만 골라서 치킨 거리 최소
*/
###