👀 문제
https://www.acmicpc.net/problem/1759
👊 도전
1. 설계
- 사전 순으로 정렬해야하므로 DFS를 호출하기 전 오름차순 정렬한다.
- DFS를 이용하여 l개를 뽑고, 최소 한 개의 모음과 최소 두 개의 자음이 있는지 확인한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int l, c;
static String[] array;
static boolean[] visit;
public static void dfs(String s, int start, int depth) {
if(depth==l) {
check(s);
return;
}
for(int i=start;i<c;i++) {
if(visit[i]) continue;
visit[i]=true;
dfs(s+array[i], i+1, depth+1);
visit[i]=false;
}
}
public static void check(String s) {
int ja=0, mo=0;
for(int i=0;i<l;i++) {
Character now=s.charAt(i);
if(now=='a'||now=='e'||now=='i'||now=='o'||now=='u') mo++;
else ja++;
}
if(mo>=1&&ja>=2) System.out.println(s);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
l=scan.nextInt();
c=scan.nextInt();
array=new String[c];
for(int i=0;i<c;i++)
array[i]=scan.next();
visit=new boolean[c];
Arrays.sort(array);
dfs("",0,0);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용하여 모든 경우를 구한다
- 사전식으로 출력해야하므로 DFS를 호출하기 전 Arrays.sort()를 이용해 오름차순 정렬한다.
- dfs의 파라미터 s는 지금까지 생성한 암호, start는 체크해야할 인덱스, depth는 생성한 암호 길이 수 이다.
- depth==l이되면 check()를 통해 모음과 자음 개수를 확인한다. 조건에 맞다면 출력한다.
- visit[]를 이용하여 문자의 중복 사용을 피한다.
- visit[i]=true라면 이미 사용한 문자이므로 패스, false라면 사용을 위해 true로 변환 후 재귀호출로 다음 문자를 찾으로 가고, 암호 생성을 끝낸 후 다시 돌아오면 다음 사용을 위해 false로 초기화한다.