딩코딩 : Computer Science 블로그

#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 data[10], tmp[10];

void divide(int lt, int rt){
	int mid, p1, p2, p3;
	if(lt<rt){
		mid = (lt+rt)/2;
		divide(lt, mid);
		divide(mid+1, rt);
		p1=lt;
		p2=mid+1;
		p3=lt;
		while(p1<=mid && p2<=rt){
			if(data[p1]<data[p2]) tmp[p3++]=data[p1++];
			else tmp[p3++]=data[p2++];
		}
		while(p1<=mid){
			tmp[p3++]=data[p1++];
		}
		while(p2<=rt){
			tmp[p3++]=data[p2++];
		}			
		for(int i=lt; i<=rt; i++){
			data[i] = tmp[i];
		}
		
		
	}
		
}


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

#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;	
}

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

using namespace std;


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,i,arr[31],order=1,pos=1,cnt=0;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &arr[i]);
	}
	stack<int> s;
	string ans = "";
	for(i=1;i<=n;i++){
		s.push(arr[i]);
		ans+='P';
		
		while(!s.empty()&&s.top()==order){
			ans+='O';
			order++;
			s.pop();
		}
	}
	
	if(s.empty()) printf("%s\n",ans.c_str());
	else printf("impossible\n");

	return 0;	
}

기차 교차로 문제

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

using namespace std;

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	vector<int> v;
	
	
	while(n>0){
		v.push_back(n%k);
		n = n/k;
	}	
	for(i=v.size()-1; i>=0; i--){
		if(v[i]>=10){
			printf("%c", ('A'+(v[i]-10)));
		}
		else printf("%d",v[i]);
	}
	
	return 0;	
}

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

using namespace std;

int stack[100], top=-1;
void push(int x){
	stack[++top] = x;
}
int pop(){
	return stack[top--];
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	char str[20]="0123456789ABCDEF";
	while(n>0){
		push(n%k);
		n = n/k;
	}
	while(top!=-1){
		printf("%c",str[pop()]);
	}
	
	return 0;	
}