[코딩테스트] 문자열 지옥에 빠진 호석 (DFS)

문제

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.
  하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

예제 입력 1

3 3 2
aaa
aba
aaa
aa
bb

예제 출력 1

56
0

예제 입력 2

3 4 3
abcb
bcaa
abac
aba
abc
cab

예제 출력 2

66
32
38

생각

• 문제가 길고 복잡하게 '환형'에 대해 설명되어 있지만,, 결국 이동 시 map 범위(0~N-1, 0~M-1) 넘어가면 반대편 끝으로 넘어가면 된다
• 인덱스 1부터 시작하면 헷갈려서 문제 풀 떄 0부터 시작하게 하고 풀었다!
  • (0,0) 위치에서 (-1, -1)만큼 이동 = (-1 + N, -1 + M) 위치로 이동
  • (N-1, M-1) 위치에서 (1, 0)만큼 이동 = (N-1+1 -N, M-1)= (0, M-1) 위치로 이동

int dx = (x + d[0] + N) % N;
int dy = (y + d[1] + M) % M;

• target 문자열을 만들 수 있는지 순서대로 check해야 하므로 깊이 우선 탐색(DFS)를 사용하였다
• 문자열의 길이가 최대 5글자라서 혹시,, 메모이제이션 없어도 되나? 하고 시도했으나 바로 시간초과가 발생했다. 그래서 메모이제이션도 적용해보았다.

memo[n][m][l] = (n, m) 위치에서 시작하여 타겟의 l 번째 문자에 도달했을 떄까지의 경우의 수

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class StringHell {

    private static int N, M, K;
    private static char[][] map;
    private static int[][][] memo;
    private static final int MAX_WORD_LENGTH = 5;

    static final int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

    public int DFS(int L, int x, int y, char[] target) {
        if (L == target.length - 1) {
            return 1;
        }
        if (memo[x][y][L] != -1) {
            return memo[x][y][L];
        }

        int cnt = 0;
        for (int[] d : dir) {
            int dx = (x + d[0] + N) % N;
            int dy = (y + d[1] + M) % M;
            if (map[dx][dy] == target[L + 1]) {
                cnt += DFS(L + 1, dx, dy, target);
            }
        }

        memo[x][y][L] = cnt;
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        StringHell T = new StringHell();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nums = br.readLine().split(" ");
        N = Integer.parseInt(nums[0]);
        M = Integer.parseInt(nums[1]);
        K = Integer.parseInt(nums[2]);

        map = new char[N][M];
        memo = new int[N][M][MAX_WORD_LENGTH];

        for (int n = 0; n < N; n++) {
            char[] words = br.readLine().toCharArray();
            for (int m = 0; m < M; m++) {
                map[n][m] = words[m];
            }
        }

        for (int i = 0; i < K; i++) {
            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    for (int l = 0; l < MAX_WORD_LENGTH; l++) {
                        memo[n][m][l] = -1;
                    }
                }
            }
            char[] target = br.readLine().toCharArray();
            int cnt = 0;
            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    if (map[n][m] == target[0]) {
                        cnt += T.DFS(0, n, m, target);
                    }
                }
            }
            System.out.println(cnt);
        }
    }

}

• 채점 결과
  1행: 메모이제이션 적용 / 2행: 메오이제이션 미적용
  

---

문제 출처