Note) DFS와 BFS의 단점
- DFS는 인접행렬의 크기가 커져서, 순회하는 트리의 구조가 깊어질수록
탐색이 상당히 느려지는 단점이 있음.
- BFS의 경우, 인접행렬이 커질수록 큐의 크기도 기하급수적으로 커짐.
즉, 메모리의 사용량이 상당히 증가함.
- 순회하는 트리의 깊이와도 상관없으며, 메모리 사용량도 줄일순 없을까?
Def) Backtracking
- 탐색하는 도중에, 지금의 서브 트리에 정답이 없을거 같다면
해당 서브 트리를 더이상 순회하지 않고 되돌아 가는 기법
- 이런 방식을 가지치기(Prunning)이라 함.
- 어떤 노드의 유망성(Promising)을 판단하여, 유망하지 않다면
해당 노드를 가지치기하고, 부모 노드로 되돌아감(Backtraing)
Note) Backtracking을 적용해야 하는 경우
- 일정한 크기의 조건들이 주어지고, 그 안에서 완전 탐색을 통해
최적 경로 또는 최적 비용을 탐색해야 하는 경우.
- 각 조건에서 선택할 수 있는 경우의 수가 정해져 있을 경우
ex. 2차원 배열, etc...
Thm) Backtraking 기본 코드
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101
};
int g_nDepth;
int g_nResMat[MAX_COUNT];
void BT(int _nCurrDepth);
int main(void)
{
int nStartDepth = 0;
scanf("%d", &g_nDepth);
BT(nStartDepth);
return 0;
}
void BT(int _nCurrDepth)
{
size_t i;
if (g_nDepth == _nCurrDepth) {
for (i = 0; i < g_nDepth; ++i) printf("%d ", g_nResMat[i]);
printf("\n");
}
else {
for (i = 0; i < g_nDepth; ++i) {
g_nResMat[_nCurrDepth] = i;
BT(_nCurrDepth + 1);
// g_nResMat[_nCurrDepth - 1] = FALSE;
}
}
}
Note) 순열
정해진 임의의 집합에서 다른 순서로 섞는 연산을 뜻함.
n 개를 가진 집합 내에서 n개를 고르는 순열의 개수는 n!이 됨.
<hide/>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum { N = 3, R = 3 };
int in[N] = { 0, 1, 2 };
void print(vector<int>& v)
{
for (int i : v)
{
cout << i << ' ';
}
cout << endl;
}
void p(int selected, vector<int>& v)
{
if (R == selected)
{
print(v);
}
else
{
for (int i = selected; i < N; ++i)
{
swap(v[selected], v[i]);
p(selected + 1, v);
swap(v[selected], v[i]);
}
}
}
int main(void)
{
vector<int> v;
v.reserve(N);
for (int i = 0; i < N; ++i)
{
v.push_back(in[i]);
}
p(0, v);
return 0;
}
Note) 순열의 반복문 버전
- next_permutation / prev_permutation
next_permutation: 오름차순의 배열을 기반으로 순열을 만들어줌.
prev_permutation: 내림차순의 배열을 기반으로 순열을 만들어줌.
...
do {
/* TODO */
} while(next_permutation(v.begin(), v.end()));
...
Note) 조합
순서에 관계없이 n개를 고르는 것.
<hide/>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum { N = 5, R = 3 };
void print(vector<int> v)
{
for (int i : v)
{
cout << i << ' ';
}
cout << endl;
}
void c(int selected, vector<int> v)
{
if (R == v.size())
{
print(v);
}
else
{
for (int i = selected + 1; i < N; ++i)
{
v.push_back(i);
c(i, v);
v.pop_back();
}
}
}
int main(void)
{
vector<int> v;
v.reserve(N);
c(-1, v);
return 0;
}
Ex) 주사위 n개의 모든 경우의 수
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101
};
int g_nDepth;
int g_nResMat[MAX_COUNT] = {0,};
void BT(int _nCurrDepth);
int main(void)
{
int nStartDepth = 0;
scanf("%d", &g_nDepth);
BT(nStartDepth);
return 0;
}
void BT(int _nCurrDepth)
{
size_t i;
if (g_nDepth == _nCurrDepth) {
for (i = 0; i < g_nDepth; ++i) printf("%d ", g_nResMat[i]);
printf("\n");
} else {
for (i = 1; i <= 6; ++i) {
g_nResMat[_nCurrDepth] = i;
BT(_nCurrDepth + 1);
// g_nResMat[_nCurrDepth - 1] = FALSE;
}
}
}<hide/>
// TestCase
3
// Expected
1 1 1
1 1 2
1 1 3
...
6 6 5
6 6 6
Ex) 세 주사위 눈의 합이 n 이상인 경우 출력
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101
};
int g_nDepth = 3, g_nSum;
int g_nResMat[MAX_COUNT] = {0,};
void BT(int _nCurrDepth, int _nSum);
int main(void)
{
int nStartDepth = 0;
scanf("%d", &g_nSum);
BT(nStartDepth, 0);
return 0;
}
void BT(int _nCurrDepth, int _nSum)
{
size_t i;
if (g_nDepth == _nCurrDepth)
{
if (g_nSum <= _nSum)
{
for (i = 0; i < g_nDepth; ++i)
{
printf("%d ", g_nResMat[i]);
}
printf("\n");
}
}
else
{
for (i = 1; i <= 6; ++i)
{
g_nResMat[_nCurrDepth] = i;
BT(_nCurrDepth + 1, _nSum + i);
// g_nResMat[_nCurrDepth - 1] = FALSE;
}
}
}<hide/>
// TestCase
16
// Expected
4 6 6
5 5 6
5 6 5
5 6 6
6 4 6
6 5 5
6 5 6
6 6 4
6 6 5
6 6 6
Ex) 동아리 회장선거
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
};
int g_nDepth;
int g_nResMat[MAX_COUNT] = {0,};
void BT(int _nCurrDepth);
int main(void)
{
int nStartDepth = 0;
scanf("%d", &g_nDepth);
BT(nStartDepth);
return 0;
}
void BT(int _nCurrDepth)
{
size_t i;
if (g_nDepth == _nCurrDepth) {
for (i = 0; i < g_nDepth; ++i) {
if (0 == g_nResMat[i]) {
printf("O");
}
else {
printf("X");
}
}
printf("\n");
}
else {
for (i = 0; i <= 1; ++i) {
g_nResMat[_nCurrDepth] = i;
BT(_nCurrDepth + 1);
// g_nResMat[_nCurrDepth - 1] = FALSE;
}
}
}<hide/>
// TestCase
3
// Expected
OOO
OOX
OXO
OXX
XOO
XOX
XXO
XXX
Ex) 순열 구하기
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
};
int g_nKind, g_nDepth;
int g_nResMat[MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uCnt = 0;
void print_permutation(int _nKind, int _nDepth);
void BT(int _nCurrDepth);
int main(void)
{
int nStartDepth = 0;
scanf("%d %d", &g_nKind, &g_nDepth);
print_permutation(g_nKind, g_nKind - g_nDepth);
BT(nStartDepth);
return 0;
}
void print_permutation(int _nKind, int _nDepth)
{
int nNumerator = 1, nDenominator = 1;
size_t i;
for (i = 1; i <= _nKind; ++i) nNumerator *= i;
for (i = 1; i <= _nDepth; ++i) nDenominator *= i;
printf("%d\n", nNumerator / nDenominator);
}
void BT(int _nCurrDepth)
{
size_t i;
if (g_nDepth == _nCurrDepth) {
for (i = 0; i < g_nDepth; ++i) {
printf("%c", g_nResMat[i] + 'A'); // 5. 목표 깊이에 도달하면, 출력.
}
printf("\n");
}
else {
for (i = 0; i < g_nKind; ++i) {
if (TRUE == g_nVisitMat[i]) continue; // 1. 방문한 숫자는 다음숫자로 넘어감.
g_nVisitMat[i] = TRUE; // 2. 숫자 방문 처리.
g_nResMat[_nCurrDepth] = i; // 3. 결과 배열에 정수 저장.
BT(_nCurrDepth + 1); // 4. 다음 깊이로 이동.
g_nVisitMat[i] = FALSE; // 6. 부모 노드 전환 후 재방문을 위해 초기화.
}
}
}<hide/>
// TestCase
4 2
// Expected
12
AB
AC
AD
BA
BC
BD
CA
CB
CD
DA
DB
DC
Ex) 이진수 순열
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101
};
int g_nDepth, g_nSum;
int g_nResMat[MAX_COUNT];
void BT(int _nCurrDepth, int _nSum);
int main(void)
{
int nStartDepth = 0;
scanf("%d %d", &g_nDepth, &g_nSum);
BT(nStartDepth, 0);
return 0;
}
void BT(int _nCurrDepth, int _nSum)
{
size_t i;
if (g_nDepth == _nCurrDepth) {
if (g_nSum == _nSum)
{
for (i = 0; i < g_nDepth; ++i) {
printf("%d", g_nResMat[i]);
}
printf(" ");
}
}
else {
for (i = 0; i < 2; ++i) {
g_nResMat[_nCurrDepth] = i;
BT(_nCurrDepth + 1, _nSum + i);
}
}
}<hide/>
// TestCase
3 2
// Expected
011 101 110
Ex) 리모컨
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DEGREE = 6
};
int g_nKind, g_nDepth;
int g_nResMat[MAX_COUNT] = {0,}, g_nVisitMat[MAX_COUNT] = {0,};
int g_nDirMat[DEGREE] = {10, 5, 1, -1, -5, -10};
int g_nStartTemp, g_nTargetTemp, g_nMinCnt = INT_MAX, g_nCnt = 0;
void BT(int _nCurrTemp);
int main(void)
{
scanf("%d %d", &g_nStartTemp, &g_nTargetTemp);
g_nVisitMat[0] = TRUE;
BT(g_nStartTemp);
printf("%d", g_nMinCnt);
return 0;
}
void BT(int _nCurrTemp)
{
int i;
if (g_nTargetTemp == _nCurrTemp) {
if (g_nCnt < g_nMinCnt) g_nMinCnt = g_nCnt;
return;
}
else {
for (i = 0; i < DEGREE; ++i) {
if (abs(g_nTargetTemp - _nCurrTemp - g_nDirMat[i]) < abs(g_nTargetTemp - _nCurrTemp))
{
++g_nCnt;
g_nVisitMat[_nCurrTemp + g_nDirMat[i]] = TRUE;
BT(_nCurrTemp + g_nDirMat[i]);
--g_nCnt;
g_nVisitMat[_nCurrTemp + g_nDirMat[i]] = TRUE;
}
}
}
}<hide/>
// TestCase
7 34
// Expected
5
Ex) 오른편 절단 가능 소수
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
};
int g_nDepth;
int g_nCnt = 0;
int isPrime(int _n);
void BT(int _nCurrNum, int _nLen);
int main(void)
{
scanf("%d", &g_nDepth);
// 1의 자리를 소수로 시작
BT(2, 1); BT(3, 1); BT(5, 1); BT(7, 1);
printf("%d", g_nCnt);
return 0;
}
int isPrime(int _n)
{
int i;
if (_n < 2) return FALSE;
for (i = 2; i * i < _n; ++i) {
if (_n % i == 0) return FALSE;
}
return TRUE;
}
void BT(int _nCurrNum, int _nLen)
{
int i;
if (g_nDepth == _nLen) {
if (0 == _nCurrNum) return;
int nFlag = 1;
int nTemp = _nCurrNum;
while (0 != nTemp) {
if (FALSE == isPrime(nTemp)) return;
nTemp /= 10;
}
++g_nCnt;
printf("%d\n", _nCurrNum);
return;
}
else {
if (isPrime(_nCurrNum)) {
// 최고 자리 수를 제외한 다른 자리 수는 모두 홀수임.
BT(_nCurrNum * 10 + 1, _nLen + 1);
BT(_nCurrNum * 10 + 3, _nLen + 1);
BT(_nCurrNum * 10 + 7, _nLen + 1);
BT(_nCurrNum * 10 + 9, _nLen + 1);
}
}
}<hide/>
// TestCase
2
// Expected
23
29
31
37
53
59
71
73
79
9
Ex) N-Queen
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 15
};
int g_nDepth = 0, g_nCnt = 0;
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
void BT(int _nCurrDepth);
int main()
{
int nStartDepth = 0;
scanf("%d",&g_nDepth);
BT(nStartDepth);
printf("%d",g_nCnt);
return 0;
}
void BT(int _nCurrDepth)
{
int i, j;
if(_nCurrDepth==g_nDepth) // 8. 원하는 갯수만큼 놓이면 출력.
{
g_nCnt++;
return;
}
else
{
for(i=0; i<g_nDepth; i++)
{
if(g_nVisitMat[_nCurrDepth][i]) // 7. 공격(방문) 가능한 위치이면 다음칸으로
continue;
++g_nAdjMat[_nCurrDepth][i]; // 1. 퀸을 놓음.
for(j=_nCurrDepth+1; j<g_nDepth; j++) // 2. 해당 위치를 기준으로 공격(방문) 가능한 곳 표시
{
++g_nVisitMat[j][i]; // 3. 퀸의 바로 아래
if(0 <= i-(j-_nCurrDepth))
++g_nVisitMat[j][i-(j-_nCurrDepth)]; // 4. 퀸의 좌측 아래
if(i+(j-_nCurrDepth) <= g_nDepth - 1)
++g_nVisitMat[j][i+(j-_nCurrDepth)]; // 5. 퀸의 우측 아래
}
BT(_nCurrDepth+1); // 6. 백트래킹
--g_nAdjMat[_nCurrDepth][i]; // 9. 재방문을 위한 해제
for(j=_nCurrDepth+1; j<g_nDepth; j++)
{
--g_nVisitMat[j][i];
if(0 <= i-(j-_nCurrDepth))
--g_nVisitMat[j][i-(j-_nCurrDepth)];
if(i+(j-_nCurrDepth) <= g_nDepth - 1)
--g_nVisitMat[j][i+(j-_nCurrDepth)];
}
}
}
}<hide/>
// TestCase
4
// Expected
2
Ex) 체커 도전
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 13
};
int g_nDepth = 0;
int g_nAdjMat[MAX_COUNT] = {0,};
int g_nVisitMat[3][3 * MAX_COUNT] = {0,};
size_t g_uCnt = 0;
void BT(int _nCurrDepth)
{
size_t i;
if(_nCurrDepth==g_nDepth)
{
if(g_uCnt<3)
{
for(i=0; i<g_nDepth; i++)
{
printf("%d ", g_nAdjMat[i]);
}
printf("\n");
}
g_uCnt++;
}
else
{
for(i=1; i<=g_nDepth; i++)
{
if(!g_nVisitMat[0][i]&&!g_nVisitMat[1][i+_nCurrDepth]&&!g_nVisitMat[2][g_nDepth+i-_nCurrDepth])
{
g_nVisitMat[0][i]=g_nVisitMat[1][i+_nCurrDepth]=g_nVisitMat[2][g_nDepth+i-_nCurrDepth] = TRUE;
g_nAdjMat[_nCurrDepth]=i;
BT(_nCurrDepth+1);
g_nVisitMat[0][i]=g_nVisitMat[1][i+_nCurrDepth]=g_nVisitMat[2][g_nDepth+i-_nCurrDepth] = FALSE;
}
}
}
}
int main()
{
int nStartDepth = 0;
scanf("%d", &g_nDepth);
BT(nStartDepth);
printf("%zu", g_uCnt);
}<hide/>
// TestCase
6
// Expected
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
Ex) 암호만들기
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
using namespace std;
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 15
};
int g_nDepth = 0, g_nCharCnt = 0;
int g_nResMat[MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
char g_nInputStr[MAX_COUNT] = {0,};
void BT(int _nCurrDepth);
int main(void)
{
int nStartDepth = 0;
size_t i, cnt = 0;
char strInput[MAX_COUNT] = {0,};
scanf("%d %d", &g_nDepth, &g_nCharCnt);
for (i = 0; i < g_nCharCnt; ++i) scanf(" %c", &g_nInputStr[i]);
sort(g_nInputStr, g_nInputStr + g_nCharCnt);
BT(nStartDepth);
return 0;
}
void BT(int _nCurrDepth)
{
size_t i;
if (g_nDepth == _nCurrDepth)
{
size_t uGatherCnt = 0, uConsonantCnt = 0;
for (i = 0; i < g_nDepth; ++i)
{
if ('a' == g_nResMat[i] || 'e' == g_nResMat[i] ||
'i' == g_nResMat[i] || 'o' == g_nResMat[i] ||
'u' == g_nResMat[i])
{
++uGatherCnt;
}
else
{
++uConsonantCnt;
}
}
if (1 <= uGatherCnt && 2 <= uConsonantCnt)
{
for (i = 0; i < g_nDepth; ++i)
{
printf("%c", g_nResMat[i]);
}
printf("\n");
}
}
else
{
for (i = 0; i < g_nCharCnt; ++i)
{
if (TRUE == g_nVisitMat[i] || g_nInputStr[i] < g_nResMat[_nCurrDepth - 1]) continue;
g_nVisitMat[i] = TRUE;
g_nResMat[_nCurrDepth] = g_nInputStr[i];
BT(_nCurrDepth + 1);
g_nVisitMat[i] = FALSE;
}
}
}<hide/>
// TestCase
3 5
m o u s e
// Expected
ems
mos
msu
// TestCase
4 6
a t c i s w
// Expected
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw
Ex) 치즈
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
using namespace std;
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DIRECTION = 8
};
size_t g_uVRowCnt, g_uVColCnt;
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1} };
void DFS(size_t _nVCurrRow, size_t _nVCurrCol);
int main(void)
{
size_t i, j, uVStartRow = 1, uVStartCol = 1;
scanf("%zu %zu ", &g_uVRowCnt, &g_uVColCnt);
for (i = 1; i <= g_uVRowCnt; ++i) {
for (j = 1; j <= g_uVColCnt; ++j) {
scanf("%d", &g_nAdjMat[i][j]);
}
}
DFS(uVStartRow, uVStartCol);
printf("%zu %zu\n", g_uVRowCnt, g_uVColCnt);
for (i = 1; i <= g_uVRowCnt; ++i) {
for (j = 1; j <= g_uVColCnt; ++j) {
printf("%d ", g_nVisitMat[i][j]);
}
printf("\n");
}
return 0;
}
void DFS(size_t _uVCurrRow, size_t _uVCurrCol)
{
size_t i;
g_nVisitMat[_uVCurrRow][_uVCurrCol] = TRUE;
for (i = 0; i < DIRECTION; ++i) {
size_t uVNextRow = _uVCurrRow + g_nDirMat[i][0];
size_t uVNextCol = _uVCurrCol + g_nDirMat[i][1];
if (TRUE == g_nVisitMat[uVNextRow][uVNextCol]) continue;
if (FALSE == g_nAdjMat[uVNextRow][uVNextCol] &&
1 <= uVNextRow && uVNextRow <= g_uVRowCnt &&
1 <= uVNextCol && uVNextCol <= g_uVColCnt)
{
DFS(uVNextRow, uVNextCol);
}
}
}<hide/>
#include <stdio.h>
#include <string.h>
int map[105][105];
int check[105][105];
int n, m;
int w;
void start(int x, int y){
check[y][x] = 1;
if(map[y][x] == 1){
map[y][x] = 0;
w--;
return;
}
if(x-1 != -1 && !check[y][x-1]) start(x-1, y);
if(x+1 <= m && !check[y][x+1]) start(x+1, y);
if(y-1 != -1 && !check[y-1][x]) start(x, y-1);
if(y+1 <= n && !check[y+1][x]) start(x, y+1);
}
int main(){
memset(map, -1, sizeof(map));
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d", &map[i][j]);
if(map[i][j] == 1) w++;
}
}
int day = 0, result = 0;
while(w>0){
day++;
result = w;
memset(check, 0, sizeof(check));
start(0, 0);
}
printf("%d \n%d", day, result);
return 0;
}<hide/>
// TestCase
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
// Expected
3
5
Ex) 연구활동 가는길
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 11
};
size_t g_uVCnt = 0, g_uECnt = 0;
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
int g_nSum = INT_MAX;
void solve(int _nCurrDepth, int _nSum)
{
if(_nCurrDepth==g_uVCnt)
{
if(_nSum<g_nSum) g_nSum=_nSum;
return;
}
else
{
for(int i=1; i<=g_uVCnt; i++)
{
if(!g_nVisitMat[i] && g_nAdjMat[_nCurrDepth][i])
{
g_nVisitMat[i]=TRUE;
solve(i, _nSum+g_nAdjMat[_nCurrDepth][i]);
g_nVisitMat[i]=FALSE;
}
}
}
}
int main(void)
{
int i;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for(i=0; i<g_uECnt; i++)
{
size_t uV1, uV2, uCost;
scanf("%zu %zu %zu", &uV1, &uV2, &uCost);
g_nAdjMat[uV1][uV2]=g_nAdjMat[uV2][uV1]=uCost;
}
solve(1, 0);
printf("%d\n", g_nSum==INT_MAX ? -1:g_nSum);
return 0;
}<hide/>
// TestCase
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
// Expected
149
Ex) 예산 관리
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 22
};
int g_nBudget = 0, g_nDepth = 0, g_nRes = 0;
int g_nAdjMat[MAX_COUNT] = {0,};
void f(int _nCurrDepth, int _nSum)
{
if(g_nBudget < _nSum) return;
if(g_nDepth+1 == _nCurrDepth)
{
if(_nSum <= g_nBudget && g_nRes < _nSum)
{
g_nRes = _nSum;
}
}
else
{
f(_nCurrDepth+1, _nSum+g_nAdjMat[_nCurrDepth]);
f(_nCurrDepth+1, _nSum);
}
}
int main()
{
int i;
scanf("%d %d", &g_nBudget, &g_nDepth);
for(i=1; i<=g_nDepth; i++)
{
scanf("%d", &g_nAdjMat[i]);
}
f(1, 0);
printf("%d", g_nRes);
return 0;
}<hide/>
// TestCase
40
6
7 13 17 19 29 31
// Expected
39
Ex) 회문 만들기
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 19,
PALINDROME_COUNT = 9,
};
int g_nDepth = 0, g_nCnt = 0;
int g_nVisit[MAX_COUNT] = {0,};
void BT(int _nCurrDepth);
int main()
{
scanf("%d",&g_nDepth);
BT(0);
printf("%d\n",g_nCnt);
return 0;
}
void BT(int _nCurrDepth)
{
size_t i;
if((PALINDROME_COUNT / 2) + 1 == _nCurrDepth)
{
g_nCnt++;
}
else
{
for(i=0; i<g_nDepth; i++)
{
g_nVisit[i]=TRUE;
BT(_nCurrDepth+1);
g_nVisit[i]=FALSE;
}
}
}<hide/>
// TestCase
3
// Expected
243
'C > 자료구조와 알고리듬' 카테고리의 다른 글
| Chapter 15. BFS (0) | 2021.12.02 |
|---|---|
| Chapter 14. DFS (0) | 2021.11.28 |
| Chapter 13. 그래프(Graph) (0) | 2021.11.26 |
| Chapter 12. 힙(Heap) (0) | 2021.11.25 |
| Chapter 11. 이진 탐색 트리(Binary Search Tree) (0) | 2021.11.21 |
댓글