Backtracking 백준 알고리즘 자바 1759 ‘암호 만들기’ 문제풀이

Problem

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

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

Output 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

Solution

백트래킹 알고리즘의 개념은 해결 방법을 얻을 때까지 모든 가능성을 확인해서 찾는다는 것이다. 트리 형태로 구성하며 dfs를 사용한다. 트리를 탐색할 때 원하는 해답이 아닌 경우는 현재 노드의 부모 노드로 돌아간 후 아직 방문하지 않은 노드가 있다면 다시 방문하는 형태다.
※ 참고 : 알고리즘 문제 풀이 전략 - 한빛미디어

• 입력 받은 문자를 정렬한다. (문제에서 사전식으로 정렬된 문자를 선호한다고 하였으므로)
• 예제에 따라 a부터 시작하는 4개의 문자로 이루어진 문자열, c부터 시작하는, …. w부터 시작하는 4개의 문자로 이루어진 문자열을 각각의 그래프라고 생각해본다.
• for문을 돌며 인덱스 값을 하나씩 증가시키고, 문자의 개수도 확인하며 (depth 변수) 문자열을 만든다.
• 문자의 개수가 입력 받은 값과 동일할 때 조건을 확인해본다.
  • visit[]은 문자가 선택되었는 지 확인하는 배열이다.
  • 모음의 개수를 세고, 자음의 개수를 센다.
  • 그것의 조건이 일치하면 문자열을 출력한다.
• 계속 반복하면서 가능한 모든 문자열을 출력한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
	static boolean[] visit;
	static String[] code;
	static int l, c;
	
	private static void backtracking(int start, int depth) {
		if(depth == l) {
			int vow = 0, cons = 0; String ans = "";
			for(int i = 0; i < c; i++) {
				if(visit[i]) {
					ans += code[i];
					if(code[i].equals("a") || code[i].equals("e") || code[i].equals("i") || code[i].equals("o") || code[i].equals("u")) vow++;
					else cons++;
				}
			}
			if(vow >= 1 && cons >= 2) System.out.println(ans);
			return;
		}
		
		for(int i = start; i < c; i++) {
			visit[i] = true;
			backtracking(i + 1, depth + 1);
			visit[i] = false;
		}	
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split("\\s");
		code = br.readLine().split("\\s");
		
		l = Integer.parseInt(line[0]); c = Integer.parseInt(line[1]); visit = new boolean[c];
		Arrays.sort(code);
		 
		backtracking(0, 0);
	}
}