DFS 정복!! 레벨 별

이진 트리와 멀티 트리를 생각하면서 해보고,

관리해야할 항이 몇개인지 관리해보면 된다.

 

LV 1 예산관리

row도 필요없고, 걍 순서에서 값만 비교해보면 됨

#include <stdio.h>

int B/*예산*/, n/*개수*/, act[23], res;

void f(int i, int sum)  // i번활동, i-1까지의 합계

{

if (i == n + 1)

{

if (sum <= B && sum>res) //예산 보다는 작고 현재 값보다는 크면.

res = sum;

return;

}

f(i + 1, sum + act[i]); // i번째 활동을 포함하거나

f(i + 1, sum);         // 포함하지 않 거나

}

int main() {

int i;

scanf("%d %d", &B, &n);

for (i = 1; i <= n; i++)

scanf("%d", &act[i]);

f(1, 0);

printf("%d", res);

return 0;

}

LV 2 연구활동 가는길

flag를 두어 방문했던 곳을 한번만 가게 함

#include<stdio.h>

int n, m, G[11][11], sol = 0x7fffffff, chk[11];

void solve(int V, int W)

{

if (V == n)

{

if (W<sol) sol = W;

return;

}

for (int i = 1; i <= n; i++)

if (!chk[i] && G[V][i])

{

chk[i] = 1;

solve(i, W + G[V][i]);

chk[i] = 0;

}

}

int main(void)

{

scanf("%d %d", &n, &m);

for (int i = 0; i<m; i++)

{

int s, e, w;

scanf("%d %d %d", &s, &e, &w);

G[s][e] = G[e][s] = w;

}

solve(1, 0);

printf("%d\n", sol == 0x7fffffff ? ‐1 : sol);

return 0;

}

LV 3 해밀턴 순환 회로

flag를 두고, row도 두어 처리 함

#include<stdio.h>

int N;

int map[110][110];

int sol = 0x7fffffff;

int max = 0x7fffffff;

int chk[13];

void dfs(int V, int r,int cost)

{

if (cost >= sol) return;//만약 현재값이 ??

if (V >= N)

{

if (map[r][1] == 0) { 

return; 

}

cost += map[r][1];//비용 증가

if (cost < sol) sol = cost;

return;

}

for (int i = 2; i <= N; i++)

{

if (r == i) continue;

if (!chk[i] && map[r][i])//들러보지 않은 곳

{

chk[i] = 1;

dfs(V + 1, i, cost + map[r][i]);

chk[i] = 0;

}

}

}

void main()

{

freopen("input.txt", "r", stdin);

scanf("%d", &N);

for (int i = 1; i <= N; i++)

for (int j = 1; j <= N; j++)

{

scanf("%d", &map[i][j]);

}

dfs(1, 1, 0);

printf("%d", sol != max ? sol : 0);

}