https://www.acmicpc.net/problem/1062
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net
모든 경우를 다 확인하여 계산하는 백트래킹 문제입니다.
먼저, 단어의 시작은 "anta"로 시작되고, 끝은 "tica"로 끝납니다.
따라서 시작과 끝에 사용되는 알파벳인 'a', 'c', 'i', 'n', 't'는 무조건 가르쳐야하는 알파벳입니다.
M이 5보다 작으면 무조건 모든 단어를 읽을 수 없게 되는것이고,
M이 5보다 크거나 같을 때 백트래킹을 이용하여 해결하면 됩니다.
이제 모든 알파벳을 대상으로 백트래킹을 돌립니다.
여기서 i를 0부터 돌려버리면 abcdint, adcbint와 같은 중복이 발생하므로 next문자부터 돌려줍니다.
가르친 알파벳의 갯수가 M과 같으면 단어를 읽을 수 있지 확인하고, ans을 갱신시켜주고 최종적인 답을 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static char list[][] = new char[50][16];
static boolean alpha[] = new boolean[26];
static int N, M, ans;
static void init() {
alpha['a' - 'a'] = true;
alpha['c' - 'a'] = true;
alpha['i' - 'a'] = true;
alpha['n' - 'a'] = true;
alpha['t' - 'a'] = true;
}
static void dfs(int idx, int cnt) {
if (cnt == M) {
int readCnt = 0;
for (int i = 0; i < N; i++) {
boolean chk = true;
for (int j = 0; j < list[i].length; j++) {
if (!alpha[list[i][j] - 'a']) {
chk = false;
break;
}
}
if (chk)
readCnt++;
}
ans = Math.max(ans, readCnt);
return;
}
for (int i = idx; i < 26; i++) {
if (alpha[i])
continue;
alpha[i] = true;
dfs(i + 1, cnt + 1);
alpha[i] = false;
}
}
static void func() {
if (M < 5) {
System.out.println(0);
return;
}
init();
dfs(0, 5);
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 15650 N 과 M (2) (0) | 2021.01.26 |
|---|---|
| boj 15649 N 과 M (1) (0) | 2021.01.26 |
| boj 2580 스도쿠 (0) | 2021.01.22 |
| boj 1759 암호 만들기 (0) | 2021.01.22 |
| boj 9663 N-Queen (0) | 2021.01.22 |