딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/1238

문제 내용에서

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 

1번 노드에 있는 사람은2번 노드를 거쳤다가 

다시 1번노드로 돌아와야 한다.

이 거리를 구해주기 위해 각각의 노드에서 2번 노드까지 가는데 필요한 거리와

2번노드에서 각각의 노드에 가는데 필요한 거리를 더해주면 된다.

#include <bits/stdc++.h>

using namespace std;

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);
	
	int n, m, x, i, a,b,c,j,k;
	scanf("%d %d %d",&n,&m,&x);
	vector<pair<int, int> > map[n+1];

	vector<int> dist2(n+1, INT_MAX); 
	vector<int> ans(n+1, 0);
	priority_queue<Edge> Q;

	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a].push_back(make_pair(b,c));
	}

	for(i=1; i<=n; i++){
		Q.push(Edge(i,0));
		dist2[i] = 0;
		while(!Q.empty()){
			int cur_node = Q.top().node;
			int cur_dist = Q.top().cost;
		
			Q.pop();
		
			if(dist2[cur_node] < cur_dist) continue;
				for(j=0; j<map[cur_node].size();j++){
				int next_node = map[cur_node][j].first;
				int next_dist = map[cur_node][j].second;
			
				Q.push(Edge(next_node, cur_dist+next_dist));
				if(dist2[next_node]> cur_dist+next_dist){
					dist2[next_node] = cur_dist+next_dist;
				}
			
			}
		
		}

		if(i==x){
			for(k=1; k<=n; k++){
				ans[k] += dist2[k];
			}
		}
		else{
			ans[i] += dist2[x];
		}
		
		fill(dist2.begin(), dist2.end(), INT_MAX);
		
	}
	
	printf("%d\n", *max_element(ans.begin(),ans.end()));
}

첫 코드

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

https://www.acmicpc.net/problem/4195

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

using namespace std;

int unf[200002], sizes[2000002];

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

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for(int T=0; T<t; T++){
		int a;
		map<string, int> m;
		int node = 1;
		string s1, s2;
		cin >> a;
		
		for(int i=0; i<200002;i++){
			unf[i] = i;
			sizes[i] = 1;
		}
		
		
		for(int i=0; i<a; i++){
			cin >> s1 >> s2;
			if(m.count(s1)==0) m[s1]=node++;
			if(m.count(s2)==0) m[s2]=node++;
			
			Union(m[s1],m[s2]);
			
			
			cout << max(sizes[Find(m[s1])], sizes[Find(m[s2])]) << '\n';
			
		}
	}
	
	
}

https://www.acmicpc.net/problem/1717

#include <stdio.h>
#include <iostream>

using namespace std;

int unf[1000002];
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(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i,n, m,a,b,c;
	scanf("%d %d",&n,&m);
	
	for(i=1; i<=n; i++){
		unf[i] = i;
	}
	
	
	for(i=0; i<m; i++){
		scanf("%d %d %d", &a,&b,&c);
		if(a==1){
			int v1 = Find(b);
			int v2 = Find(c);
			if(v1==v2) printf("YES\n");
			else printf("NO\n");
		}
		else{
			int v1 = Find(b);
			int v2 = Find(c);
			if(v1!=v2){
				Union(b,c);
			}
		}
	}
	
}

집합을 나타내는 방법을

union & find 알고리즘을 이용하여 풀 수 있다.

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

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

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