딩코딩 : Computer Science 블로그

첫 코드

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

int n,m, arr[51][51], ch[20], minn=INT_MAX;
vector<pair<int,int> > v;

void DFS(int node){
	if(node==m){
		int cnt=0;
		//도시 피자배달 거리 구하기  
		//ch[i]==1 이면 선택된 피잣집 
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				int min_dist=INT_MAX;
				if(arr[i][j]==1){
					for(int k=0; k<v.size(); k++){
						if(ch[k]==1){
							int cur_dist = abs(i-v[k].first)+abs(j-v[k].second);
							if(min_dist>cur_dist){
								min_dist = cur_dist;
							}
							
						}
						else continue;
					}
					cnt += min_dist;
				}
			}
			
		} 
		if(cnt<minn) minn=cnt;
		
	}
	else{
		for(int i=0; i<v.size(); i++){
			if(ch[i]==0){
				ch[i]=1;
				DFS(node+1);
				ch[i]=0;
			}
		}	
		
	}
	
}

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

	// 피잣집 선택 갯수 
	// 6개중 4개 선택 ---> 거리 최솟값 
	
	int i,j;
	// 피잣집 벡터 
	
	
	scanf("%d %d",&n, &m);
	
	
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			scanf("%d",&arr[i][j]);
			
			if(arr[i][j]==2) {
				v.push_back(make_pair(i, j));
			}
		}
	}
	// 피잣집 선택  
	DFS(0);
	
	printf("%d",minn);
	
}

문제점

1. 피잣집을 구할 때 순열로 뽑았다. DFS에서 경우의수가 불필요하게 많이 계산된다.

2. 필요한 정보는 집과 피자집의 좌표인데 그 외의 불필요한 좌표를 모두 돌면서 시간이 오래걸린다.

1차 수정

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

int n, m, ch[20], minn=INT_MAX;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;

void DFS(int s, int L){
	if(L==m){
		int cnt = 0;
		for(int i=0; i<hs.size(); i++){
			int hs_min =INT_MAX;
			for(int j=0; j<pz.size(); j++){
				if(ch[j]==0) continue;
				int hs_dist = abs(hs[i].first-pz[j].first) + abs(hs[i].second - pz[j].second);
				if(hs_min> hs_dist) hs_min = hs_dist;
			}
			cnt += hs_min;	
		}
		if(minn>cnt) 
		{
			minn=cnt;

		}
	}
	else{
		//피자집 순열 구함  
		for(int i=s; i<pz.size(); i++){
			ch[i] = 1;
			DFS(i+1, L+1);
			ch[i] = 0;
		}
	}
}


int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j,tmp;
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			scanf("%d", &tmp);
			if(tmp==1){
				hs.push_back(make_pair(i,j));
			}
			else if(tmp==2){
				pz.push_back(make_pair(i,j));
			}
		}	
	}
	
	DFS(0,0);
	printf("%d",minn);
	
	
}

ch배열에 해당하는 피잣집 인덱스를 직접 넣는게 아니라

피잣집 인덱스가 해당하면 표시해주는 방법으로 했다.

ch[0] = 1 이면 0번 피잣집이 조합에 포함되고, ch[1] = 0 이면 1번 피잣집은 조합에 포함되지 않는 걸로 지정했다.

이렇게하면 반드시 체크를 해제해주는 과정이 필요하다.

ch배열에 해당 피잣집 인덱스를 직접 넣어주면 더 간단하게 풀 수 있다.

예를들어 ch[0] = 1 ch[1] = 2 ch[2] = 3 이렇게하면 1번, 2번, 3번 피잣집이 해당한다.

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

int n, m, ch[20], minn=INT_MAX;
vector<pair<int, int> > hs;
vector<pair<int, int> > pz;

void DFS(int s, int L){
	if(L==m){
		int cnt = 0;
		for(int i=0; i<hs.size();i++){
			int hs_min = INT_MAX;
			for(int j=0; j<m; j++){
				int dist =abs(pz[ch[j]].first - hs[i].first) + abs(pz[ch[j]].second - hs[i].second);
				if(hs_min > dist) hs_min = dist;
			}
			cnt+=hs_min;
		}
		if(minn>cnt) minn = cnt;
	}
	else{
		//피자집 순열 조합  구함  
		for(int i=s; i<pz.size(); 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);
	int i, j,tmp;
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			scanf("%d", &tmp);
			if(tmp==1){
				hs.push_back(make_pair(i,j));
			}
			else if(tmp==2){
				pz.push_back(make_pair(i,j));
			}
		}	
	}
	
	DFS(0,0);
	printf("%d",minn);
	
	
}

ch 배열에 직접 해당 피잣집의 인덱스를 넣어주니 코드가 더 간결해졌다.

순열 조합 문제

https://dingcoding.tistory.com/entry/%EB%B0%B1%EC%A4%80-15650%EB%B2%88-N%EA%B3%BC-M-2-%EC%88%9C%EC%97%B4%EC%9D%98-%EC%A1%B0%ED%95%A9-%EB%AC%B8%EC%A0%9C-DFS%EB%A1%9C-%ED%92%80%EA%B8%B0

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://flexboxfroggy.com/#ko

css flex를 응용해서 공부해보기 좋은 사이트입니다.

하단에 24번 답있습니다.

css를 입력해서

개구리를 원하는 방법으로 배치하는 게임입니다.

24번 답

flex-direction:column-reverse;
flex-wrap:wrap-reverse;
align-content:space-between;
justify-content:center;

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를 돌면서 수식이 성립하는지 확인해주었다.

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

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

<input type="checkbox" name="" id="modal-switch">
    <label for="modal-switch">
        <span>
            modal 열고 닫기
        </span>
   	</label>

html에서 체크박스에 포함된 글자를 눌러도

체크박스가 선택되도록 하려면

체크박스에 id를 지정해주고

<label for="체크박스 id">

label의 for에다 적어주면 된다.

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

int n,r,ch[20],path[20],cnt;
vector<int> v;

//----


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

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tmp;
	
	scanf("%d %d",&n,&r);
	for(int i=0; i<n; i++){
		scanf("%d", &tmp);
		v.push_back(tmp);
	}
	DFS(0);
	printf("%d",cnt);
}

DFS를 활용해 순열을 구할 수 있다.

간선의 갯수를 1부터 n-1까지 탐색하면서

최적의 경로를 찾는다.

다익스트라 알고리즘과 달리 간선의 값이 음수여도 사용이 가능하다.

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

int dist[101];
struct Edge{
	int s;
	int e;
	int val;
	Edge(int a, int b, int c){
		s=a;
		e=b;
		val=c;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i,n,m,a,b,c,j,s,e;
	vector<Edge> Ed;
	scanf("%d %d", &n, &m);
	
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a,&b,&c);
		Ed.push_back(Edge(a,b,c));
	}
	for(i=1; i<=n; i++){
		dist[i]=INT_MAX;
	}
	scanf("%d %d",&s,&e);
	dist[s]=0;
	for(i=1; i<n; i++){
		for(j=0; j<Ed.size(); j++){
			int s=Ed[j].s;
			int e=Ed[j].e;
			int w=Ed[j].val;
			if(dist[s]!=INT_MAX && dist[s]+w<dist[e]){
				dist[e]=dist[s]+w;
			}
		}

	}
	for(j=0; j<Ed.size();j++){
		int u=Ed[j].s;
		int v=Ed[j].e;
		int w=Ed[j].val;
		if(dist[u]!=INT_MAX && dist[u]+w<dist[v]){
			printf("-1\n");
			return 0;
		}
		
	}
	
	printf("%d\n", dist[e]);
	return 0;

}