[백준] 2186번. 문자판(JAVA)

문제

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

---

풀이(32분)

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

public class Main {

    static int n, m, k;
    static String target;
    static char[][] map;
    static int[][][] dp;
    static int[] dx = new int[]{0, 0, -1, 1}; // 상하좌우
    static int[] dy = new int[]{-1, 1, 0, 0};

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

        // 입력 받기
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new char[n][m];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        target = br.readLine();
        dp = new int[n][m][target.length() + 1];

        // DP 배열 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        // 정답 누적
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == target.charAt(0)) {
                    answer += dfs(i, j, 1);
                }
            }
        }

        System.out.println(answer);
    }

    static int dfs(int row, int col, int depth) {
        if (depth == target.length()) {
            return 1;
        }

        if (dp[row][col][depth] != -1) {
            return dp[row][col][depth];
        }

        dp[row][col][depth] = 0;

        for (int dir = 0; dir < 4; dir++) {
            for (int step = 1; step <= k; step++) {
                int nextRow = row + dx[dir] * step;
                int nextCol = col + dy[dir] * step;

                if (!isInBounds(nextRow, nextCol)) break;

                if (map[nextRow][nextCol] == target.charAt(depth)) {
                    dp[row][col][depth] += dfs(nextRow, nextCol, depth + 1);
                }
            }
        }

        return dp[row][col][depth];
    }

    static boolean isInBounds(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m;
    }
}

---

문제 풀이 전략

 

어떻게 보면 dp를 이용한 간단한 문제이다.

그중에서도 중요 포인트는 dp 배열을 이용하여 이미 체크된 지점에 대해 중복되게 계산을 하지 않는 것이다.

-> 이를 통해 불필요한 연산을 대폭 줄일 수 있다.

 

그 외에는 k라는 스텝을 적용하여 연산을 진행하는 것 외에는 별다른 특이사항이 없다.

물론, k가 존재하지 않았다면? dp를 적용하지 않아도 될 수도 있다. n, m의 범위가 그렇게 크지 않기 때문이다.

하지만 k라는 스텝이 존재하여 하나의 점에 대해 수많은 탐색이 추가로 이루어져야 하기 때문에 dp가 꼭 필요하다!