[백 트래킹] BOJ 1759 암호 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

문제 해결 알고리즘

 

1. 처음에 a, b를 입력 받고, 배열(v)에 모든 알파벳들을 다 넣고 정렬을 해준다.

 

2. dfs(n, x, y, pos)함수를 실행한다. 

int n : 글자 수

int x : 모음 수

int y : 자음 수

int pos : 마지막 글자의 배열(v)에서의 위치

 

3. dfs 함수에서 n이 a와 같아지고 x가 1 이상 y가 2 이상일 때, 암호를 출력해준다.

만약 n이 a와 다르다면, pos부터 배열(v)의 마지막 원소 까지 for문을 돌려주면서 배열(arr)의 다음 글자를 입력해준다.

이때, 입력한 다음 글자가 모음이면, x에 1을 더해주고, 자음이면, y에 1을 더해주면서 계속 dfs함수를 실행해준다.

 

 

 

소스 코드

 

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

int a, b;
char v[20];
char arr[16];

void dfs(int n, int x, int y, int pos){

  if(n == a){
    if(x >= 1 && y >= 2){
      for(int i=0;i<a;i++){
        cout << arr[i];
      }
      cout << '\n';
    }
    return;
  } 
  else{
    for(int i=pos;i<b;i++){
      arr[n] = v[i];
      if(v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u') dfs(n+1,x+1,y,i+1);
      else dfs(n+1,x,y+1,i+1);
    }
  }

}
int main(){
  cin >> a >> b;
  for(int i=0;i<b;i++){
    cin >> v[i];
  }

  sort(v, v+b);

  dfs(0,0,0,0);
}

 

메모

 

이 알고리즘을 생각하기까지는 오랜 시간이 걸리진 않았으나, 자꾸 Segmentation fault 오류가 났다.

계속 고민하다가 배열(v)를 벡터로 설정하고 정렬을 해서 그런 오류가 발생한 것 같다. 소스 코드에 나온 것처럼 배열로 설정하고 정렬하니 문제 없이 잘 돌아갔다.