자바칩
[백준 / Java] 1759: 암호 만들기 (백트래킹) 본문
난이도: Gold 5
문제: https://www.acmicpc.net/problem/1759
문제
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
출력
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.
내가 자신없는 백트래킹이고, 골드5라서 어려울 줄 알았는데 1차원 배열의 백트래킹이라 그런지 생각보다 쉽게 풀렸다.
문제에 주어진 데이터는 이러하다.
4 6
a t c i s w
L(암호의 알파벳 소문자 개수) = 4
C(문제에 주어진 알파벳 소문자 개수) = 6
문제에 주어진 알파벳 소문자 C개를 입력받을 1차원 배열 arr을 선언하고, 차례대로 값을 초기화시킨다.
그리고 이 배열을 Arrays.sort(arr) 메서드를 사용해서 오름차순 정렬시킨다.
정렬된 arr 배열은 다음과 같다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| arr[index] | a | c | i | s | t | w |
L은 4니까, 정렬된 4개의 문자열을 순서대로 뽑는다면 다음과 같다.
| index | 암호 문자열 |
| 0123 | acis |
| 0124 | acit |
| 0125 | aciw |
| 0134 | acst |
| 0145 | actw |
| 0234 | aist |
| 0235 | aisw |
| 0245 | aitw |
| 0345 | astw |
| 1234 | cist |
| 1235 | cisw |
| 1245 | citw |
| 1345 | cstw |
| 2345 | istw |
여기서 빨간색 문자열을 주의깊게 보자.
문제에서 암호는 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 했다.
그런데 cstw는 모음이 한 개도 없으므로 답에서 제외해야 한다.
결국 최종적으로 cstw를 제외한 나머지가 답이 된다.
그리고 인덱스를 주의깊게 보자.
인덱스가 앞에서부터 차례대로 되어있는데, 뒤에있는 인덱스들만 점점 바뀌지 않는가?
바로 이것이 백트래킹으로 풀어야 하는 이유이다.
백트래킹으로 0번째부터 L - 1번째까지 알파벳을 찾아서 파고들다가, L번째에 도달하면 최종 암호를 구하고, 다시 돌아가서 L - 1번째 알파벳을 다시 찾으러 가고, L - 1번째 알파벳의 인덱스를 끝까지 탐색했다면 L - 2번째로 다시 돌아가서 알파벳을 찾으러가고....의 반복이다.
가장 처음에 호출하는 것이므로, dfs 메서드의 인수로 depth = 0와 index = 0을 넘겨준다.
index(0)번째 인덱스부터 배열을 탐색해서 depth(0)번째 알파벳을 찾으러 간다.
전체 dfs 메서드의 구현을 보기 전에 dfs 메서드의 일부인 백트래킹 알고리즘의 핵심 코드를 보자.
for (int i = index; ...)
이 부분이 정말 중요하다.
이렇게 하지 않으면 dfs 메서드를 재귀 호출해면 다시 0번째 인덱스부터 찾게 되므로 시간 초과가 발생할 수도 있다.
이제 dfs 메서드의 전체 코드를 보자.
if (depth == L)
이 부분도 백트래킹의 핵심 알고리즘이다.
dfs 메서드를 재귀로 계속 파고들었다가 L번째에 도달하면 최종 암호를 구해서 함수를 종료시켜야 한다.
dfs 메서드로 그동안 구해온 암호를 바로 출력하기 전에, 구해온 암호에 모음 1개와 자음 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1759_암호만들기 {
static int L, C; // L: 암호의 알파벳 소문자 개수, C: 문제에 주어진 알파벳 소문자 개수
static char[] arr; // 1차원 알파벳 소문자 C개를 담은 배열
static boolean[] visited; // 1차원 방문 체크 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new char[C];
visited = new boolean[C];
st = new StringTokenizer(br.readLine());
// 1차원 알파벳 소문자 C개를 담은 배열 초기화
for (int i = 0; i < C; i++) {
arr[i] = st.nextToken().charAt(0);
}
Arrays.sort(arr); // 알파벳 소문자 C개를 담은 배열 오름차순 정렬
dfs(0, 0); // index(0)번째 인덱스부터 배열을 탐색해서 depth(0)번째 알파벳을 찾으러가기
}
// index번째 인덱스부터 배열을 탐색해서 depth번째 알파벳 찾기
public static void dfs(int depth, int index) throws IOException {
// 깊이가 L(암호의 알파벳 소문자 개수)과 같다면 암호를 다 찾은 것
if (depth == L) {
char[] pwd = new char[L]; // 1차원 암호 알파벳 소문자 L개를 담은 배열
int j = 0; // 암호 알파벳 소문자 L개를 담은 배열의 인덱스를 증가시키는 임시 변수
// 알파벳 소문자 C개를 담은 배열 모두 탐색
for (int i = 0; i < C; i++) {
if (visited[i]) { // 해당 알파벳을 방문했다면
// 암호를 담는 배열에 해당 알파벳 추가 후
// 암호를 담는 배열 인덱스 1 증가
pwd[j++] = arr[i];
}
}
boolean vowel = false; // 모음(a, e, i, o, u) 존재 여부
int consonant = 0; // 자음 개수
// 암호 알파벳 소문자 L개를 담은 배열 모두 탐색
for (int i = 0; i < L; i++) {
// 해당 알파벳이 모음(a, e, i, o, u)이라면
if (pwd[i] == 'a' || pwd[i] == 'e' || pwd[i] == 'i'
|| pwd[i] == 'o' || pwd[i] == 'u') {
vowel = true; // 모음 존재 여부를 true로 변경
} else { // 해당 알파벳이 자음이라면
consonant++; // 자음 개수 1 증가
}
}
// 모음이 존재하고, 자음 개수가 2개 이상이라면
if (vowel && consonant >= 2) {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String result = new String(pwd); // 암호를 담은 배열을 문자열로 변환
bw.write(result + "\n"); // 암호 문자열 출력
bw.flush();
}
return; // 알파벳 L개로 구성된 암호 1개를 찾았으므로 메서드 종료 후 다음 암호 찾으러 가기
}
// 알파벳 소문자 C개를 담은 배열을 매개변수로 받은 index부터 탐색
// => index 이전까지의 알파벳은 이미 앞에서 찾았기 때문
for (int i = index; i < C; i++) {
if (!visited[i]) { // 해당 알파벳을 아직 방문하지 않았다면
visited[i] = true; // 해당 알파벳 방문 체크
// index(i + 1)번째 인덱스부터 배열을 탐색해서 depth(depth + 1)번째 알파벳을 찾으러가기
dfs(depth + 1, i + 1);
visited[i] = false; // 해당 알파벳 방문 해제
}
}
}
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 / Java] 2023: 신기한 소수 (백트래킹) (0) | 2024.07.21 |
|---|---|
| [백준 / Java] 1759: 섬의 개수 (BFS) (0) | 2024.07.20 |
| [백준 / Java] 15683: 감시 (백트래킹, 구현) (1) | 2024.07.17 |
| [백준 / Java] 3184: 양 (BFS) (0) | 2024.07.14 |
| [백준 / Java] 1303: 전쟁 - 전투 (BFS) (0) | 2024.07.14 |
