딩코딩 : Computer Science 블로그

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

1. 문제 설명

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며,
최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

별이 n개 주어지고 별들의 각각 좌표가 주어진다.

모든 별을 이용해서 최소 거리, 비용으로 별자리를 만들어야한다.

2. 접근 방법[알고리즘]

최소 비용으로 모든 별을 이어야 하므로 최소스패닝트리, 최소 신장 트리(MST)를 만들어야한다.

크루스칼 알고리즘이나 프림 알고리즘을 사용해서 만들면 된다.

나는 크루스칼 알고리즘을 이용했다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

struct Edge{
	int v1;
	int v2;
	double val;
	Edge(int a, int b, double c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(const Edge &b) const{
		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;
}

double dist(pair<double, double> &a , pair<double, double> &b){
	return sqrt(pow(a.first-b.first,2) + pow(a.second - b.second,2));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Edge> Q;
	double res=0;
	int n;
	vector<pair<double, double> > star;
	
	cin >> n;
	for(int i=0; i<n; i++){
		double x,y;
		cin >> x >> y;
		star.push_back(make_pair(x,y));
	}
	
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			Q.push(Edge(i,j, dist(star[i],star[j])));
		}
	}
	
	for(int i=0; i<n; i++){
		unf[i] = i;
	}
	
	
	while(!Q.empty()){
		int node_a = Q.top().v1;
		int node_b = Q.top().v2;
		double d = Q.top().val;
		Q.pop();
		
		if(Find(node_a)!=Find(node_b)){
			Union(node_a, node_b);
			res += d;
		}		
	}
	cout << fixed;
	cout.precision(3);
	cout << res ;
	
	
}

문제에서 출력을 절대/상대 오차 10-2까지 허용한다고 해서

아예 소수 세번째 자리까지 출력했다.

출력과정에서 반올림이 될 수도 있다고 생각해서 널널하게 세번째까지 출력했다.

input을 star에 입력해주었다.

그리고 모든 star 요소에 대해서 각 거리를 구해 우선순위 큐(최소힙)에 넣고

두 별 사이의 거리가 최소인 Edge를 최소힙에서 꺼내서 Union&Find 알고리즘을 이용하여

이미 두 별이 연결되어 있으면 넘어가고, 연결되어 있지 않으면 연결해주고

그 두 별 사이의 거리를 res 변수에 더해주었다.

최소스패닝트리를 구하는 걸 연습하기 좋은 문제다.

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

#include <bits/stdc++.h>
using namespace std;

int n, r;
int ch[20];
// 1 2 3
// 1 고르거나 안고르거나
// 2 고르거나 안고르거나
// 3 고르거나 안고르거나
// -> 끝고른거 갯수가 r 이면 출력 아니면 그냥 리턴

void DFS(int num, int selected){
	if(num > n) return;
	if(selected==r){
		for(int i=1; i<=n; i++){
			if(ch[i]==1){
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}
	else{
		ch[num+1] = 1;
		DFS(num+1, selected+1);
		ch[num+1] = 0;
		DFS(num+1, selected);
	}
}
 

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r;
	
	DFS(0,0);
}

#include <bits/stdc++.h>
using namespace std;

int n, r;
int ch[20];
// 1 2 3
// 1 고르거나 안고르거나
// 2 고르거나 안고르거나
// 3 고르거나 안고르거나
// -> 끝고른거 갯수가 r 이면 출력 아니면 그냥 리턴

void DFS(int s, int L){
	if(L==r){
		for(int i=0; i<L; i++){
			printf("%d ",ch[i]);
			
		}
		printf("\n");
	}
	else{
		for(int i=s; i<=n; i++){
			ch[L] = i;
			DFS(i+1, L+1);
		}
		
	}
}

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r;
	
	DFS(1,0);
}

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

1. 문제 설명

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

2. 접근 방법[알고리즘]

DFS를 돌면서 +. -. 공백 기호중 하나를 선택하고

숫자를 다 사용한 경우, 계산결과가 0이 된다면 출력해준다.

3.문제 풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int L;
char path[20];

int cal(){
	int ans=0;
	int cur =0;
	char op='+';
	
	for(int i=0; i<=L; i++){
		if(path[i]=='-'||path[i]=='+'||path[i]=='\0'){
			if(op=='-'){
				ans-=cur;
				cur=0;
			}
			else if(op=='+'){
				ans+=cur;
				cur=0;
			}
			op = path[i];
		}
		else{
			if(path[i]==' '){
				cur*=10;
			}
			else cur += (path[i]-'0');
		}
	
	}

	return ans;
}


void DFS(int cur, int end){
	if(cur==end+1){
		if(cal()==0){
			for(int i=0; path[i]!='\0'; i++){
				printf("%c", path[i]);
			}
			printf("\n");
		}
		
		return;
	}
	else{
		if(cur==end){
			path[L++] = cur+'0';
			DFS(cur+1, end);
			L-=1;
		}
		else{
			
			path[L++] = cur+'0';
			path[L++] = ' ';
			DFS(cur+1, end);
			L-=2;
			
			
			
			path[L++] = cur+'0';
			path[L++] = '+';
			DFS(cur+1, end);
			L-=2;
	
		
			path[L++] = cur+'0';
			path[L++] = '-';
			DFS(cur+1, end);
			L-=2;	
		
		}
	}
	
	
	
}

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t,i,tmp;
	scanf("%d",&t);
	vector<int> input;
	
	for(i=0; i<t; i++){
		int tmp;
		scanf("%d", &tmp);
		input.push_back(tmp);
	}
	
	for(i=0; i<input.size();i++){
		L=0;
		DFS(1, input[i]);
		printf("\n");
	}
	
	
	
}

DFS를 돌면서 계산식을 path에 넣어준다.

숫자를 다 사용한 경우에는 cal 함수를 이용해 계산 결과가 0인지 확인 해주고 옳다면 출력해준다.

처음에는 DFS를 만들 때 돌면서 바로바로 계산을 해주려 했는데,

연산자에 +, - 만 있는게 아니라 공백까지 포함되어, 그럴 경우 계산을 올바르게 하기 힘들다.

그래서 아예 숫자를 다 사용한 후에 계산식이 0에 해당하는지 확인하여 출력해주도록 했다.

만약에 연산자에 공백이 있는 경우가 아니라면, 매개변수에 결괏값을 넘겨주면서 DFS를 돌면서 계산까지 함께 되도록

만들 수 있다.

그리고 문제 조건 중

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다.

이 조건은 DFS를 만들 때

맨 처음 공백을 넣어주고 ,+, - 순으로 돌면 해결 된다.

만약 이게 헷갈리다면

벡터나 배열에 결괏값을 일일이 저장해주고,

sort한 후에 하나씩 출력하는 방법도 있다.

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

DFS 문제를 풀다가 복면산 이라는 단어를 처음 봤다.

1. 복면산 뜻

수학 퍼즐의 일종으로, 계산식에서 숫자를 문자나 그림 등으로 가려놓고 어떤 숫자가 들어가는지 알아맞히는 퍼즐이다. 숫자가 마치 복면을 쓰고 있는 것 같다고 하여 복면산이라고 부른다.

더 알아보기 : https://namu.wiki/w/%EB%B3%B5%EB%A9%B4%EC%82%B0

간단하게 말하면

     SEND

 + MORE

----------

  MONEY

이런 알파벳으로 된 수식이 존재할 때 각 알파벳애 대응되는 숫자를 찾아내야 하는 문제이다.

2. 접근 방법[알고리즘]

SEND+MORE = MOENY

연산에 들어가는 알파벳 갯수는 8개이다.

각 알파벳마다 숫자는 0~9중 하나가 들어갈 수 있고,

0~9 까지는 한 번씩 만 쓰일 수 있다.

이 문제의 조건에서는 send , more , money의 맨 앞 숫자가 0이어도 인정한다.

S에 0부터 9까지 하나씩 넣어보고,

E에 S에 넣은 숫자를 제외한 0~9까지 하나씩 넣어보고

N에 S와 E에 넣은 숫자를 제외한 0~9까지 하나씩 넣어보고...

...

이렇게 모든 알파벳에 각 숫자를 매칭하고,

SEND+MORE = MONEY 수식이 성립하는지 확인한다.

수식이 성립하는 경우가 있을 때, YES를 출력하고 아니면 NO를 출력한다.

이렇게 탐색해보기 위해 DFS 알고리즘을 이용한다.

3.문제 풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;
//ch는 알파벳에 해당하는 숫자 저장,
//num에는 0~9가 쓰였는지 저장 
int ch[30] , num[10], cnt=0;

string a, b, c;
map<char, int> m;
bool flag; 


void DFS(int cur, int end){
	if(flag) return;
	if(cur==end){
		int i,send=0,more=0, money=0;
		for(i=0; i<a.length(); i++){
			send = send*10 + ch[m[a[i]]];
		}
		for(i=0; i<b.length(); i++){
			more = more*10 + ch[m[b[i]]];
		}
		for(i=0; i<c.length(); i++){
			money = money*10 + ch[m[c[i]]];
		}
		if((send+more)==money){ 
			flag=true;
//			cnt++;
//			cout << cnt << "번------"<<'\n';
//			
//			cout<<send<<'\n';
//			cout<<more<<'\n';
//			cout<<money<<'\n';
//			cout<<"----------------"<<'\n';
		}
		
		return;
	}
	else{		
		for(int i=0; i<=9;i++){
			if(num[i]==0){
				num[i]=1;
				ch[cur] = i;
				DFS(cur+1, end);
				num[i]=0;
			}
		}
	}
}



int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,node=0;
	cin >> a >> b >> c;

	
	for(i=0; i<a.length(); i++){
		if(m.count(a[i])==0) m[a[i]]=node++;
	}
	for(i=0; i<b.length(); i++){
		if(m.count(b[i])==0) m[b[i]]=node++;
	}
	for(i=0; i<c.length(); i++){
		if(m.count(c[i])==0) m[c[i]]=node++;
	}
	
	DFS(0,node);
	
	if(flag) cout << "YES\n";
	else cout << "NO\n";

}

우선 단어를 입력 받고,

입력받은 단어에 대해

map을 이용해 등장하는 알파벳에 순서를 지정해주었다.

그리고 위에서 설명한 것 처럼 각 알파벳마다 숫자를 대응 시키고

DFS를 돌면서 수식이 성립하는지 확인해주었다.

주석이 달린 부분은 만약에 수식이 성립한다면

어떤 숫자들로 성립되는지 표기해 주는 부분이다.

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

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 알고리즘을 이용하여 풀 수 있다.