딩코딩 : Computer Science 블로그

첫 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int ch[30], dist[30];

struct Edge{
	int node, cost;
	Edge(int a, int b){
		node = a;
		cost = b;
	}
	bool operator<(const Edge &b) const{
		return cost > b.cost;
	}
	
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<Edge> map[30];
	
	int n,m,a,b,c,i;
	
	for(i=2; i<30; i++){
		dist[i] = INT_MAX;
	}
	
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a].push_back(Edge(b,c));
	}
	
	
	
	priority_queue<Edge> Q;
	//Edge(노드, 1에서부터 거리)
	 
	Q.push(Edge(1,0));
	
	
	while(!Q.empty()){
		auto cur = Q.top();
		Q.pop();
		
		if(cur.cost==INT_MAX) break;
		if(ch[cur.node]==0){
			ch[cur.node] = 1;
			dist[cur.node] = cur.cost;
			
			for(i=0; i<map[cur.node].size(); i++){
				Q.push(Edge(map[cur.node][i].node, cur.cost + map[cur.node][i].cost));				
			}
		}
		
	}
	
	
	for(i=2; i<=n; i++){
		if(dist[i]==INT_MAX){
			printf("%d : impossible\n", i);
		}
		else printf("%d : %d\n", i, dist[i]);
	}
	
}

우선순위 큐에서 빠져나오면 해당 정점의 dist값이 최소인게 분명해서

해당 정점을 check 해주고 다시 방문하지 않게 해주었다.

해설 코드에서는 정점이 check여부를 사용하지 않고,

해당정점의 cost값이 현재 dist 배열에 있는 값보다 크다면 continue 해서

그 정점에서 다른 정점으로 이동하지 않게 처리했다.

해설 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

struct Edge{
	int vex, dis;
	Edge(int a, int b){
		vex = a;
		dis = b;
	}
	bool operator<(const Edge &b)const{
		return dis>b.dis;	
	}
	
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, n, m, a, b, c;
	scanf("%d %d",&n,&m);
	
	vector<pair<int, int > > graph[30];
	vector<int> dist(n+1, INT_MAX);
	priority_queue<Edge> Q;
	
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a,&b,&c);
		graph[a].push_back(make_pair(b,c));
	}
	
	Q.push(Edge(1,0));
	
	dist[1]=0;
	while(!Q.empty()){
		int now = Q.top().vex;
		int cost = Q.top().dis;
		Q.pop();
		
		if(cost > dist[now]) continue;
		
		for(i=0; i<graph[now].size();i++){
			int next = graph[now][i].first;
			int nextDis = cost+graph[now][i].second;
			
			if(dist[next]>nextDis){
				dist[next] = nextDis;
				Q.push(Edge(next, nextDis));
			}
				
		}

	}
	
	
	for(i=2; i<=n; i++){
		if(dist[i]==INT_MAX){
			printf("%d : impossible\n", i);
		}
		else printf("%d : %d\n", i, dist[i]);
	}
	
}

크루스칼 알고리즘은 간선에 집중하여 최소스패닝트리를 구하고,

프림 알고리즘은 노드에 집중해서 최소 스패닝 트리를 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <queue>

using namespace std;

int ch[30],V,E;

bool check(){
	for(int i=1; i<=V; i++){
		if(ch[i]==0) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i,a,b,c,ans=0;
	
	vector<pair<int,int> > v[30];
	
	scanf("%d %d",&V, &E);
	for(i=0; i<E; i++){
		scanf("%d %d %d",&a, &b, &c);
		v[a].push_back(make_pair(b,c));
		v[b].push_back(make_pair(a,c));
	}
	
	priority_queue<pair<int, int> > pQ;
	
	pQ.push(make_pair(0,1));
	
	
	while(1){
		auto cur = pQ.top();
		pQ.pop();
		int node = cur.second;
		if(ch[node]==1){
			continue;
		}
		
		ans+= -cur.first;
		ch[node] = 1;
		for(i=0; i<v[node].size(); i++){
			if(ch[v[node][i].first]==0){
				pQ.push(make_pair(-v[node][i].second, v[node][i].first));
				
			}
			
			
		}
		
		if(check()) break;
	}
	
	
	printf("%d ",ans);
	
	

	
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int ch[30];
struct Edge{
	int e;
	int val;
	Edge(int a, int b){
		e=a;
		val=b;
	}
	bool operator<(const Edge &b)const{
		return val>b.val;
	}
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	priority_queue<Edge> Q;
	vector<pair<int,int> > map[30];
	int i,n,m,a,b,c,res=0;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a, &b, &c);
		map[a].push_back(make_pair(b,c));
		map[b].push_back(make_pair(a,c));
	}
	Q.push(Edge(1,0));
	while(!Q.empty()){
		Edge tmp=Q.top();
		Q.pop();
		int v=tmp.e;
		int cost=tmp.val;
		
		if(ch[v]==0){
			res+=cost;
			ch[v]=1;
			for(i=0; i<map[v].size();i++){
				Q.push(Edge(map[v][i].first, map[v][i].second));
			}
		}		
	}
	
	printf("%d",res);
}

크루스칼 알고리즘을 이용하면

그래프에서 최소 비용의 트리를 만들어낼 수 있다.

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

int unf[10001];

struct Edge{
	int v1;
	int v2;
	int val;
	Edge(int a, int b, int c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(Edge &b){
		return val<b.val;
	}
};

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a] = b;
}

int main(){
	vector<Edge> Ed;
	int i, n, m, a, b, c, cnt=0, res=0;
	scanf("%d %d",&n, &m);
	for(i=1; i<=n; i++){
		unf[i]=i;
	}
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		Ed.push_back(Edge(a,b,c));
	}
	sort(Ed.begin(),Ed.end());
	for(i=0; i<m; i++){
		int fa=Find(Ed[i].v1);
		int fb=Find(Ed[i].v2);
		if(fa!=fb){
			res+=Ed[i].val;
			Union(Ed[i].v1, Ed[i].v2);
		}
		
	}
	printf("%d\n", res);
	return 0;
	
	
	
	
}

DFS로 푼 것

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
bool isfriend;
int n, m, ln, lm;
vector<int> map[1001];
int ch[1001];

void DFS(int s, int e){
	if(isfriend) return;
	if(s==e){
		isfriend = true;
		return;
	}
	else{
		for(int i=0; i<map[s].size(); i++){
			if(ch[map[s][i]]==0){
				ch[map[s][i]]=1;
				DFS(map[s][i], e);
				ch[map[s][i]]=0;
			}
		}	
	}
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i,a,b;
	scanf("%d %d", &n, &m);
	for(i=0;i<m;i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
		map[b].push_back(a);	
		
	}
	scanf("%d %d",&ln,&lm);
	ch[ln] = 1;
	DFS(ln, lm);
	if(isfriend) printf("YES");
	else printf("NO");
	
	return 0;	
}

dis-joint set(Union & Find 알고리즘)

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

int unf[1001];

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v] = Find(unf[v]);
	
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}



int main() {
	//freopen("input.txt.txt","rt",stdin);
	ios_base::sync_with_stdio(0);
	
	int n, m, a, b;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		unf[i]=i;
	}
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		Union(a,b);
	}
	cin>>a>>b;
	a=Find(a);
	b=Find(b);
	if(a==b) cout << "YES";
	else cout <<"NO";
	return 0;
	
	

	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
//    5C3 = 4C2 + 4C3

int dy[21][21];

int DFS(int n, int r){
	if(dy[n][r]>0) return dy[n][r];
	if(r==0 || n==r) return 1;
	else{
		return dy[n][r] = DFS(n-1, r-1) + DFS(n-1, r);
	}
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d", DFS(n,r));
	return 0;	
}

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);

	}
	
	
}