[백준] 20166번 : 문자열 지옥에 빠진 호석

문제

 

 

접근 방식

 

 

 

문제에 나오는 환형의 개념 중에서 대각선 이동이 살짝 햇갈렸던 문제인데

위의 사진들처럼 대각선 이동 중 인덱스를 벗어나는 상황을 살펴보면

인덱스가 음수가 되는 경우에는 가장 아래줄의 왼쪽이나 오른쪽으로 한칸 이동

양수가 되는 경우에는 가장 첫줄의 왼쪽이나 오른쪽으로 한칸 이동해주면 된다.

 

나머지 상하좌우 이동도 환형을 생각해주면서 백트래킹으로 단어를 조합만 해주고

이를 맵을 사용해서 각 단어별로 카운팅을 해줬다.

 

설명은 이해가 잘 안갔는데 막상 풀어보니 난이도 자체는 어렵지 않았던 문제다.

 

풀이

public class Main {

	private static int n;
	private static int m;
	private static int min = Integer.MAX_VALUE;
	private static int max = 0;

	private static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
	private static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
	private static char[][] world;
	private static char[] chars;
	private static boolean[][] isUsed;

	private static Map<String, Integer> wordCount = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		world = new char[n][m];
		isUsed = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			world[i] = br.readLine().toCharArray();
		}

		String[] favorites = new String[k];

		for (int i = 0; i < k; i++) {
			String word = br.readLine();
			favorites[i] = word;
			max = Math.max(word.length(), max);
			min = Math.min(word.length(), min);
		}

		chars = new char[max];

		for (int i = 0; i < world.length; i++) {
			for (int j = 0; j < world[i].length; j++) {
				if (isUsed[i][j]) continue;
				isUsed[i][j] = true;
				chars[0] = world[i][j];
				makeWord(1, i, j);
				isUsed[i][j] = false;
			}
		}

		for (String favorite : favorites) {
			Integer count = wordCount.get(favorite);
			sb.append(count != null ? count : 0).append("\n");
		}

		System.out.println(sb);
	}

	private static void makeWord(int size, int x, int y) {
		if (size >= min) {
			String word = new String(Arrays.copyOfRange(chars, 0, size));
			wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
		}

		if (size == max) return;

		for (int dir = 0; dir < 8; dir++) {
			int nx = dx[dir] + x;
			int ny = dy[dir] + y;

			if (nx < 0) nx = n - 1;
			if (nx >= n) nx = 0;
			if (ny < 0) ny = m - 1;
			if (ny >= m) ny = 0;

			isUsed[nx][ny] = true;
			chars[size] = world[nx][ny];
			makeWord(size + 1, nx, ny);
			isUsed[nx][ny] = false;
		}
	}
}