백준 15811번 : 복면산?! - 복면산 DFS 문제

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

15811번: 복면산?!

 

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

1. 복면산 뜻

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

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

 

 

간단하게 말하면

 

     SEND

 + MORE

----------

  MONEY

 

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

 

 

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

 

S	E	N	D	M	O	R	Y
?	?	?	?	?	?	?	?

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

 

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

 

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