딩코딩 : Computer Science 블로그

Data라는 구조체를 만들고,

구조체를 자료형으로 갖는 벡터를 만들어서

priority queue를 문제 풀이에 이용했다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
struct Data{
	int money;
	int when;
	Data(int a, int b){
		money=a;
		when=b;
	}
	bool operator<(Data &b){
		return when>b.when;
	}
	
	
};

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,i,j,a,b,res=0, maxx=INT_MIN;
	vector<Data> T;
	priority_queue<int> pQ;
	scanf("%d", &n);
	for(i=1; i<=n ;i++){
		scanf("%d %d", &a, &b);
		T.push_back(Data(a,b));
		if(b>maxx) maxx=b;
		
	}
	sort(T.begin(), T.end());
	j=0;
	for(i=maxx; i>=1; i--){
		for(;j<n; j++){
			if(T[j].when<i) break;
			pQ.push(T[j].money);
		}
		if(!pQ.empty()){
			res+=pQ.top();
			pQ.pop();
		}
	}
	printf("%d\n",res);
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
struct Loc{
	int x, y, z;
	Loc(int a, int b, int c){
		x=a;
		y=b;
		z=c;	
	}
	bool operator<(const Loc &b)const{
		if(x!=b.x) return x<b.x;
		if(y!=b.y) return y<b.y;
		if(z!=b.z) return z<b.z;
		
	}
};


int main() {
	//freopen("input.txt.txt","rt",stdin);
	vector<Loc> XY;
	XY.push_back(Loc(2,3,5));
	XY.push_back(Loc(3,6,7));
	XY.push_back(Loc(2,3,5));
	XY.push_back(Loc(5,2,3));
	XY.push_back(Loc(3,1,6));
	
	
	for(auto pos : XY) {
		cout<<pos.x<<" "<<pos.y<<" "<<pos.z<<endl;
	}
	
	printf("---------------\n");
	
	sort(XY.begin(),XY.end());
	

	for(auto pos : XY) {
		cout<<pos.x<<" "<<pos.y<<" "<<pos.z<<endl;
	}
}

최대힙

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

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int a;
	priority_queue<int> pQ;
	while(true){
		scanf("%d",&a);
		if(a==-1) break;
		if(a==0){
			if(pQ.empty()) printf("-1\n");
			else{
				printf("%d\n",pQ.top());
				pQ.pop();
			}
		}
		else pQ.push(a);

	}
	
	
}

최소힙

최소힙은 최대힙을 구하는 것을 이용하여

부호에 마이너스를 붙여주면 구할 수 있다.

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

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int a;
	priority_queue<int> pQ;
	while(true){
		scanf("%d",&a);
		if(a==-1) break;
		if(a==0){
			if(pQ.empty()) printf("-1\n");
			else{
				printf("%d\n",pQ.top());
				pQ.pop();
			}
		}
		else pQ.push(a);

	}
	
	
}

#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