[백준_1759번] 암호 만들기

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

1759번: 암호 만들기

[문제]

 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

[코드]

import java.util.*;

public class BaekJoon_1759 {
	public static char[] alpabet;
	public static boolean[] visited; // 방문 여부 체크 배열
	public static int l,c;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		l=sc.nextInt();
		c=sc.nextInt();
		alpabet=new char[c];
		visited=new boolean[c];
		
		for(int i=0;i<c;i++)
			alpabet[i]=sc.next().charAt(0);
		
		Arrays.sort(alpabet);
		
		dfs(0,0);
	}
	
	// dfs 함수
	public static void dfs(int start, int depth) {
		// 선택된 알파벳의 개수가 입력된 문자의 개수와 같아진 경우
		if(depth==l) {
			int cons=0; // 자음 갯수
			int vow=0; // 모음 갯수
			StringBuilder sb=new StringBuilder();
			
			for(int i=0;i<c;i++) {
				// 방문 배열을 확인하여 방문한 알파벳은 저장
				if(visited[i]==true) {
					sb.append(alpabet[i]);
					// 모음 count
					if(alpabet[i]=='a'||alpabet[i]=='e'||alpabet[i]=='i'
							||alpabet[i]=='o'||alpabet[i]=='u')
						vow++;
					// 자음 count
					else
						cons++;
				}
			}
			// 조건에 맞다면 print
			if(vow>=1&&cons>=2)
				System.out.println(sb);
		}
		
		// 백트래킹
		for(int i=start;i<c;i++) {
			// 방문처리
			visited[i]=true;
			dfs(i+1,depth+1); // 깊이를 1 늘리고 재귀호출
			// 재귀호출이 끝났다면 다음 연산을 위해 방문 배열의 값을 되돌려준다.
			visited[i]=false;
		}
	}
}

 

[고찰]

 이번 문제는 백준의 백트래킹 파트에서 N과 M문제의 응용 버전이라고 볼 수 있었다. 처음에는 자음과 모음을 각각 다른 배열에 나눠 저장하는 방식으로 시도해봤지만 그 이후로 해결방법이 떠오르지 않아 생각을 바꿔보았다. 결론은 나올 수 있는 모든 문자열의 경우의 수에서 조건을 만족하는 문자열만 출력하면 되는 문제였다. 여기에 같은 문자가 반복해서 나올 수 없기 때문에 백트래킹을 사용하여 다음 배열부터 탐색하도록하여 해결할 수 있었다. 이때 주의할 점은 임호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측한다고 문제에 명시되어 있기 때문에 사전순으로 정렬된 배열을 사용해야 한다는 점이다.