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

https://www.acmicpc.net/problem/20166

 

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

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

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

---

1.  아이디어

 

격자의 크기와 신이 좋아하는 문자열의 길이가 작다는 점에서 깊이 우선 탐색을 이용할 수 있을 것 같았고 신이 좋아하는 문자열을 비교하는 횟수가 많고 중복될 수 있다는 점에서 미리 가능한 조합을 다 구하고 비교를 O(1)로 해결하도록 구현했다.

---

2. 문제풀이

 

신이 좋아하는 문자열의 길이가 1 ~ 5 이므로 길이가 1인 문자열부터 길이가 5인 문자열까지 격자의 각 점에서 전부 dfs를 돌렸다.

dfs과정에서 파라미터로 완성될 문자열을 StringBuilder로 들고 다니며 depth를 내려갈 때마다 뒤에 방문한 격자의 문자를 더하고 depth를 올라가면 다시 지우는 방식으로 가능한 모든 문자열 조합을 구해서 이를 HashMap에 카운팅하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static int N, M;
    private static final int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    private static final int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};
    private static char[][] matrix;
    private static final Map<String, Integer> cntMap = new HashMap<>();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        matrix = new char[N][M];
        for (int i = 0; i < N; i++) {
            matrix[i] = br.readLine().toCharArray();
        }

        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    dfs(i, j, new StringBuilder(), 0, k);
                }
            }
        }

        for (int tc = 1; tc <= K; tc++) {
            sb.append(cntMap.getOrDefault(br.readLine(), 0)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int r, int c, StringBuilder str, int len, int maxLen) {
        str.append(matrix[r][c]);

        if (len == maxLen) {
            cntMap.put(str.toString(), cntMap.getOrDefault(str.toString(), 0) + 1);
            return;
        }

        for (int dir = 0; dir < 8; dir++) {
            int nr = (r + dr[dir] + N) % N;
            int nc = (c + dc[dir] + M) % M;

            dfs(nr, nc, str, len + 1, maxLen);
            str.deleteCharAt(str.length() - 1);
        }
    }

}

---

4. 후기