1759번 / 암호 만들기 / 백트래킹

[ZZANZU]

• 백트래킹
• 탐색을 종료하고 바로 이전 분기로 돌아가는 타이밍에 방문 체크를 해지해야한다! ( == for문 종료 시점)

package example04;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Problem1759 {
	static int L, C;
	static Character[] data;
	static boolean[] visited;
	static LinkedList<String> result;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		L = sc.nextInt();
		C = sc.nextInt();

		data = new Character[C];
		visited = new boolean[C];

		for (int i = 0; i < C; i++) {
			String temp = sc.next();
			data[i] = temp.charAt(0);
		}
		
		Arrays.sort(data);
		result = new LinkedList<String>();

		for (int i = 0; i < data.length - 3; i++) {
			if (isVow(data[i])) {
				Password pwd = new Password(data[i], 1, 0, 1, "" + data[i]);
				dfs(pwd);
			} else {
				Password pwd = new Password(data[i], 1, 1, 0, "" + data[i]);
				dfs(pwd);
			}
		}
		
		for(String r : result) {
			System.out.println(r);
		}
		
	}

	public static void dfs(Password pwd) {
		Password currentPwd = pwd;

		// 0. 종료 조건 체크
		if (currentPwd.depth == L) { // 이부분을 4로 했었네;;
			if (currentPwd.con >= 2 && currentPwd.vow >= 1) {
				// 결과 저장
				result.add(currentPwd.pwd);
			}
		}

		// 1. 방문 체크
		visited[check(currentPwd.current)] = true;

		// 2. 연결된 길
		for (int i = check(currentPwd.current); i < data.length; i++) {
			// 3. 갈 수 있는 길
			if (visited[i] == false) {
				// 4. 간다.
				if (isVow(data[i])) {
					Password nextPwd = new Password(data[i], currentPwd.depth + 1, 
							currentPwd.con, currentPwd.vow + 1, currentPwd.pwd + data[i]);

					dfs(nextPwd);
				} else {
					Password nextPwd = new Password(data[i], currentPwd.depth + 1,
							currentPwd.con + 1, currentPwd.vow, currentPwd.pwd + data[i]);

					dfs(nextPwd);

				}
			}
		}
                // 백트래킹!
		visited[check(currentPwd.current)] = false;

	}

	// data 배열내에서 해당 문자의 index를 리턴한다.
	public static int check(char c) {
		for (int i = 0; i < data.length; i++) {
			if (c == data[i]) {
				return i;
			}
		}
		return -1;
	}

	// 모음 체크
	public static boolean isVow(char c) {
		if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
			return true;
		}

		return false;
	}

}

class Password {
	char current;
	int depth;
	int con; // 자음
	int vow; // 모음
	String pwd;

	public Password(char current, int depth, int con, int vow, String pwd) {
		this.current = current;
		this.depth = depth;
		this.con = con;
		this.vow = vow;
		this.pwd = pwd;
	}

	@Override
	public String toString() {
		return "Password [current=" + current + ", depth=" + depth + ", con=" + con + ", vow=" + vow + ", pwd=" + pwd
				+ "]";
	}

}