문제 조건
- 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
- 1 ≤ K ≤ 1,000, K는 자연수이다.
처음에는 문자열 길이만 보고 거의 완탐으로 문제를 풀었는데, 시간 초과가 났다
DP인가 했지만 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다고 했기 때문에 불가능 하고,
갈 수 있는 방향을 모두 탐색하는 대신 map으로 다음 문자열과 같은 곳만 탐색하도록 하는 방법을 사용했다.
이를 적용한 `틀린` 코드는 아래와 같다. => 이렇게 풀면 최악일 때 10* 10 * 1000 * 5^8 이 나온다
import java.util.*;
public class Main {
private static int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
private static int dc[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
private static int sum = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int testcase = in.nextInt();
char[][] alphabets = new char[row + 1][col + 1];
HashMap<Character, HashSet<Position>> map[][] = new HashMap[row + 1][col + 1];
for (int i = 1; i <= row; i++) {
String rowInput = in.next();
for (int j = 1; j <= col; j++) {
alphabets[i][j] = rowInput.charAt(j - 1);
map[i][j] = new HashMap<Character, HashSet<Position>>();
}
}
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
for (int d = 0; d < 8; d++) {
int newRow = i + dr[d];
int newCol = j + dc[d];
if (newRow < 1) {
newRow = row;
}
if (newCol < 1) {
newCol = col;
}
if (newRow > row) {
newRow = 1;
}
if (newCol > col) {
newCol = 1;
}
char ch = alphabets[newRow][newCol];
if (map[i][j] == null) {
map[i][j] = new HashMap<Character, HashSet<Position>>();
}
if (!map[i][j].containsKey(ch)) {
map[i][j].put(ch, new HashSet<>());
}
map[i][j].get(ch).add(new Position(newRow, newCol));
}
}
}
for (int t = 0; t < testcase; t++) {
char[] favorite = in.next().toCharArray();
int length = favorite.length;
sum = 0;
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
if (favorite[0] == alphabets[i][j]) {
findAll(1, i, j, favorite, length, row, col, alphabets, map);
}
}
}
System.out.println(sum);
}
}
private static void findAll(int index, int row, int col, char[] target, int targetLength, int maxRow, int maxCol,
char[][] alphabets, HashMap<Character, HashSet<Position>> map[][]) {
if (index == targetLength) {
sum++;
return;
}
HashSet<Position> set = map[row][col].get(target[index]);
if (set != null) {
for (Position p : set) {
int newRow = p.row;
int newCol = p.col;
findAll(index + 1, newRow, newCol, target, targetLength, maxRow, maxCol, alphabets, map);
}
}
}
}
class Position {
int row, col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
}
그래서 어차피 완전 탐색은 한 번은 꼭 해야 할텐데 방문했을 때 생긴 문자열의 수를 각각 구해서 저장한 뒤,
문자열을 입력받을 때마다 바로 리턴하는 방식으로 바꾸기로 했다. 이렇게 될 경우 시간 복잡도는 O(10* 10 * 5^8) 으로 줄어들게 된다.
import java.io.*;
import java.util.*;
public class Main {
private static final int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
private static final int dc[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
private static final int MAX_LENGTH = 5;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
int testcase = Integer.parseInt(st.nextToken());
char[][] alphabets = new char[row + 1][col + 1];
HashMap<String, Integer> map = new HashMap<>();
for (int i = 1; i <= row; i++) {
String rowInput = br.readLine();
for (int j = 1; j <= col; j++) {
alphabets[i][j] = rowInput.charAt(j - 1);
}
}
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
String createdString = Character.toString(alphabets[i][j]);
map.put(createdString, map.getOrDefault(createdString, 0) + 1);
findAll(1, i, j, row, col, map, createdString, alphabets);
}
}
for (int t = 0; t < testcase; t++) {
String favorite = br.readLine();
System.out.println(map.getOrDefault(favorite, 0));
}
}
private static void findAll(int index, int row, int col, int maxRow, int maxCol, HashMap<String, Integer> map,
String createdString, char[][] alphabets) {
if (index == MAX_LENGTH) {
return;
}
for (int d = 0; d < 8; d++) {
int newRow = row + dr[d];
int newCol = col + dc[d];
if (newRow < 1) {
newRow = maxRow;
}
if (newCol < 1) {
newCol = maxCol;
}
if (newRow > maxRow) {
newRow = 1;
}
if (newCol > maxCol) {
newCol = 1;
}
String newCreatedString = createdString + alphabets[newRow][newCol];
map.put(newCreatedString, map.getOrDefault(newCreatedString, 0) + 1);
findAll(index + 1, newRow, newCol, maxRow, maxCol, map, newCreatedString, alphabets);
}
}
}
'알고리즘 공부 > boj' 카테고리의 다른 글
| boj 2631: 줄세우기 (0) | 2021.04.01 |
|---|---|
| boj 20165: 인내의 도미노 장인 호석 (0) | 2021.03.24 |
| boj 20164: 홀수 홀릭 호석 (0) | 2021.03.24 |
| boj 11663: 선분 위의 점 (0) | 2021.03.17 |
| boj 19637: IF문 좀 대신 써줘 (0) | 2021.03.17 |