boj 20166: 문자열 지옥에 빠진 호석

문제 조건

• 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);
		}
	}
}