딩코딩 : Computer Science 블로그

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int Q[100], front=-1, back=-1, ch[10];
vector<int> map[10];
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i, a, b, x;
	for(i=1; i<=6; i++){
		scanf("%d %d",&a, &b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	Q[++back]=1;
	ch[1]=1;
	
	while(front<back){
		x=Q[++front];
		printf("%d ",x);
		for(i=0; i<map[x].size(); i++){
			if(ch[map[x][i]]==0){
				ch[map[x][i]]=1;
				Q[++back] = map[x][i];
				
			}
		}
		
		
	}
	
	
}

C++ 그래프 인접 리스트(adjency list) vector 구현

C++에서 벡터를 이용해 인접리스트를 쉽게 만들 수 있다.

vector<int> map[node개수] 
vector<int> map[시작노드].push_back(연결노드)

예를 들어 위 그림처럼 단방향그래프로

1번 정점에서 갈 수 있는 정점이 2, 3, 4 라면

map[1].push_back(2)

map[1].push_back(3)

map[1].push_back(4)

를 해주면 된다.

현재 노드에서 갈 수 있는 다음 노드를 선택 하는 방법

for(int i=0; i<map[현재노드].size(); i++){
	//현재 노드에서 갈 수 있는 노드를 선택 하는 방법
	int next_node = map[현재노드][i];
}

이렇게 노드를 선택해주면 DFS나 BFS에 활용할 수 있다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int ch[30], cnt=0, n, path[30],p1=0;
vector<int> map[30];

void DFS(int v){
	if(v==n){
		
		for(int i=0; path[i]!=0; i++){
			printf("%d ",path[i]);
		}
		printf("\n");
		cnt++;
	}
	else{
		for(int i=0; i<map[v].size(); i++){
			int vv = map[v][i];
			if(ch[vv]==0){
				ch[vv]=1;
				path[p1++]=vv;
				DFS(vv);
				p1--;
				ch[vv]=0;
				path[p1]=0;
			}
			
		}
		
	}
	
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int m,i,j,a,b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	path[p1++]=1;
	ch[1] = 1;
	DFS(1);
	
	printf("%d",cnt);
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>


using namespace std;
int n,cnt,minn=INT_MAX;
int map[21][21], ch[21];

void DFS(int v){
	if(v==n){
		if(cnt < minn){
			minn = cnt;
		}
		return;	
	}
	else{
		for(int i=1; i<=n; i++){
			if (map[v][i]>0 && ch[i]==0){
				ch[i]=1;
				cnt += map[v][i];
				DFS(i);
				ch[i]=0;
				cnt -=map[v][i];
			}
		}
	}
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int m, v, i,a,b,c;
	scanf("%d %d", &n, &m);
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a][b] = c;
	}
	
	DFS(1);
	printf("%d",minn);

}

DFS 함수의 매개변수에 결괏값을 넣어주면 

보다 간편하게 코드를 작성할 수 있다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>


using namespace std;
int n,cnt,cost=INT_MAX;
int map[21][21], ch[21];

void DFS(int v,int sum){
	int i;
	if(v==n){
		if(sum < cost) cost = sum;
	}
	else{
		for(i=1; i<=n ;i++){
			if(map[v][i]>0 && ch[i]==0){
				ch[i]=1;
				DFS(i, sum+map[v][i]);
				ch[i]=0;
			}
		}
	}
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int m, v, i,a,b,c;
	scanf("%d %d", &n, &m);
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a][b] = c;
	}
	
	DFS(1,0);
	printf("%d",cost);

}​

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int map[7][7], cnt = 0;
bool check[7][7];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void DFS(int row, int col){
	if(row==6 && col==6){
		cnt++;
		
		printf("----answer-----\n");
		for(int i=0; i<7; i++){
			for(int j=0; j<7; j++){
				printf("%d ", check[i][j]);
			}
			printf("\n");
		}
		printf("---------\n");
		
		
	}
	
	for(int i=0; i<4; i++){
		int nx = row+dx[i];
		int ny = col+dy[i];
		if(nx<0 || nx>6) continue;
		if(ny<0 || ny>6) continue;
		if(map[nx][ny] == 1 || check[nx][ny]) continue;
		check[nx][ny] = 1;
		DFS(nx,ny);
		check[nx][ny] = 0;

	}
	
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	for(int i=0; i<7; i++){
		for(int j=0; j<7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	check[0][0] = 1;
	DFS(0, 0);
	printf("%d",cnt);
}

결과

(미로)

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0
----answer-----
1 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 1
---------
----answer-----
1 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 1 1
0 0 1 1 1 1 1
---------
----answer-----
1 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 0
0 0 0 0 0 1 0
0 0 0 0 0 1 1
---------
----answer-----
1 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 1
---------
----answer-----
1 1 1 1 1 1 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 0
0 0 0 0 0 1 1
---------
----answer-----
1 1 1 1 1 1 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 1
---------
----answer-----
1 1 1 1 1 1 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 0 1 0 0
0 0 1 1 1 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 1
---------
----answer-----
1 1 1 1 1 1 1
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 0 1 0 0
0 0 1 1 1 0 0
0 0 1 0 0 1 1
0 0 1 1 1 1 1
---------
8

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int map[51][51], check[10], path[10], p1;

void DFS(int cur, int fin){
	if(cur==fin){
		for(int i=0; path[i]!=0; i++){
			printf("%d ",path[i]);
		}
		printf("\n");
	}
	else{
		for(int i=1; i<=fin; i++){
			if(map[cur][i]==1 && check[i]==0){
				path[p1++] = i;  
				check[i] = 1;
				DFS(i,fin);
				check[i] = 0;
				
				p1--;
				path[p1] = 0;
			}
		}		
	}
	
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, m, i, j, a,b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			printf("%d ",map[i][j]);
		}
		printf("\n");
		
	}
	check[1] = 1;
	path[p1++] = 1;
	DFS(1,n);
	
	return 0;	
}

output

-- 그래프 -- 
0 1 1 1 0
1 0 1 0 1
0 0 0 1 0
0 1 0 0 1
0 0 0 0 0

-- 탐색 path--
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,ch[20];

//후위순회 출력 
void D(int L){
	if(L==n+1){
		for(int i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ",i);
		}
		printf("\n");
	}
	else{
		ch[L]=1;
		D(L+1);
		
		ch[L]=0;
		D(L+1);	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	D(1);

	return 0;	
}

부분집합 찾기

-----

활용

합이 같은 부분집합 찾기

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,arr[11],ch[20],sum;
bool already_yes = false;
void DFS(int x){
	if(already_yes) return;
	if(x==n + 1){
		int half = 0;
		for(int i=1; i<=n; i++){
			if(ch[i]==1){
				half+=arr[i];
				
				//printf("%d ",arr[i]);
			}
		}
		//printf("\n");
		if(sum==2*half){
			printf("YES");
			already_yes = true;
			return;
		}
	}	
	else{
		ch[x] = 1;
		DFS(x+1);
		
		ch[x] = 0;
		DFS(x+1);
	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d", &arr[i]);
		sum+=arr[i];
	}
	
	DFS(1);
	if(!already_yes) printf("NO");

	return 0;	
}

매개변수를 이용해 간결하게 표현할 수 있다

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,a[11],total=0;
bool end;
void DFS(int L,int sum){
	if(end) return;
	if(L==n+1){
		if(sum*2 == total){
			printf("YES");
			end = true;
		}
	}
	else{
		DFS(L+1, sum+a[L]);	
		DFS(L+1, sum);
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1,0);


	if(!end) printf("NO");
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;


//후위순회 출력 
void D1(int v){
	if(v>7) return;
	else{
		D1(v*2);
		D1(v*2+1);	
		printf("%d ", v);
	}
}

// 전위순회 출력  
void D2(int v){
	if(v>7) return;
	else{
		printf("%d ", v);
		D2(v*2);
		D2(v*2+1);	
	}
}

// 중위순회 출력  
void D3(int v){
	if(v>7) return;
	else{
		D3(v*2);
		printf("%d ", v);
		D3(v*2+1);	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	D1(1);
	printf("\n");
	D2(1);
	printf("\n");
	D3(1);
	printf("\n");
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;

void recur(int x){
	if(x==0) return;
	recur(x/2);
	printf("%d", x%2);
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n;
	scanf("%d", &n);
	recur(n);
	
	return 0;	
}