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

🔗 문제 링크: https://www.acmicpc.net/problem/20166

🔍 고찰 과정

dfs를 활용하여 신이 좋아하는 문자열에 도달하는 경우의 수를 구하면 될 것 같다는 생각이 들었습니다. 하지만 위 문제는 다음과 같은 변수가 존재했습니다.

 

❗️타일을 지나갔던 곳은 다시 지나갈 수 있음
❗️타일의 양끝 밑 대각선 양 끝을 넘어가는 경우는 다시 처음으로 돌아가거나 마지막으로 돌아갈 수 있음
❗️방문한 순서가 다른 경우는 서로 다른 경우로 취급함

 

위 변수를 토대로 최악의 경우에서 나올 수 있는 연산량을 계산해보면 다음과 같습니다.

🎲 타일의 최대 크기 (N과 M 각각 최대 10): 10 x 10 = 100
🎲 주어지는 신이 좋아하는 문자열의 최대 개수 k = 1000
🎲 신이 좋아하는 문자열의 최대 길이 L = 5
🎲 이동할 수 있는 경우의 수 = 8(상, 하, 좌, 우, 대각선 네 방향)
🎲 신이 좋아하는 문자열을 탐색할 때 나올 수 있는 최악의 경우의 수 = 8^L * N * M * K = 3,276,800,000 (약 33억)

즉, 일일이 다 탐색해서 경우의 수를 찾아내는 방식을 활용하면 시간복잡도 O(NxMx8^L)로 약 33억의 연산량이 필요하여 1억당 1초의 연산량을 가진 Java의 기준으로는 33초가 걸리므로 시간초과 기준에 걸립니다. 그래서 추가적으로 특정 경로를 탐색했을 때 나왔던 경우의 수를 미리 저장하고 활용하는 메모이제이션 기법을 활용하였습니다. 메모이제이션을 활용하면 시간복잡도를 O(NxMx8xL)로 줄일 수가 있어 제한 시간 안에 프로그램을 실행할 수 있습니다. (각각 8개의 방향을 8번씩 모두 살펴보는 것이 아닌 8개의 방향을 각각 한 번씩 신이 좋아하는 문자열의 길이만큼 탐색할 수 있습니다.)

 

 

작성한 코드를 기준으로 설명하자면 메모이제이션을 활용하기 위해서 정수형 삼차원 배열 memo 변수를 활용하였습니다. memo에 대한 정의는 다음과 같습니다.

memo[r][c][Idx] : 타일의 (r, c)의 위치에서 신이 주신 문자열의 현재 Idx 상태를 살필 때 나올 수 있는 경우의 수

 

이를 바탕으로 모든 경우의 수의 정보를 저장하며 신이 주신 문자열의 마지막 인덱스에 도달 했을 때 최종 카운트 1의 정보를 memo에 저장하고 반환을 해줌으로써 효율적으로 계산할 수 있도록 과정을 구현하였습니다.

 

---

✏️ 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static final String END_LINE = "\n";
    private static final int BLANK = -1;

    private static final int[] dx = {1, 1, 0, -1, -1, -1, 0, 1}; // 나올 수 있는 방향
    private static final int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    private static int n, m;
    private static char[][] board;
    private static int[][][] memo;

    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());
        board = new char[n][m];

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

        for (int t = 0; t < k; ++t) {
            String godStr = br.readLine();
            int godLen = godStr.length();
            memo = new int[n][m][godLen];

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    Arrays.fill(memo[i][j], BLANK); // 정보를 -1로 초기화
                }
            }

            int result = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (godStr.charAt(0) != board[i][j]) {
                        continue;
                    }

                    result += getResult(godStr, godLen, 1, i, j);
                }
            }

            sb.append(result).append(END_LINE);
        }

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

    private static int getResult(final String godStr, final int godLen,
                                 int step, int x, int y) {
        if (memo[x][y][step - 1] != BLANK) {
            return memo[x][y][step - 1]; // 저장된 정보 활용
        }

        if (step == godLen) {
            return memo[x][y][step - 1] = 1; // 1을 카운팅
        }

        int count = 0;

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

            if (board[nx][ny] != godStr.charAt(step)) {
                continue;
            }

            count += getResult(godStr, godLen, step + 1, nx, ny);
        }
        
        return memo[x][y][step - 1] = count; // 최종 카운팅
    }
}