[JAVA] BOJ 백준 2186번 - 문자판

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2186번: 문자판

---

2. 내가 푼 방법

DP 알고리즘을 이용하며, 만들 수 있는 단어의 개수를 저장해둠으로써 가지치기할 수 있다.

 

문자열 인덱스 위치에 따라 만들 수 있는 단어를 카운팅하기 위해 dp를 3차원 Integer 배열로 선언했다. 우선 initDP 함수에서 문자열의 0번 인덱스와 같은 문자일 때 1로 초기화하고, 그 외에는 0으로 초기화한다.

public static void initDP() {
    char s = end.charAt(0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == s) {
                dp[0][i][j] = 1;
            }
            else {
                dp[0][i][j] = 0;
            }
        }
    }
}

 

그 후, fillDP 함수에서 아직 방문한 적 없는 문자열 인덱스의 문자판 위치일 때 1부터 K 위치만큼의 상하좌우를 확인하면서 개수를 카운팅한다. dp[len][i][j]가 null이면서 현재 위치에 나와야 할 문자열과 같은 문자일 경우에 이전 문자에 대한 탐색이 이뤄진다. 재귀를 통해 이전 방문했던 값을 가져오거나 이전 문자에 대한 방문을 확인하는 과정을 거쳐, base condition인 0번째 인덱스까지 탐색이 이뤄지게 된다.

public static void fillDP() {
    int len = end.length() - 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            result += dfs(len, i, j);
        }
    }
}

public static int dfs(int len, int i, int j) {
    if (dp[len][i][j] == null) {
        dp[len][i][j] = 0;

        if (arr[i][j] == end.charAt(len)) {
            for (int k = 1; k <= K; k++) {
                for (int d = 0; d < dx.length; d++) {
                    int nx = i + dx[d] * k;
                    int ny = j + dy[d] * k;

                    if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                    dp[len][i][j] += dfs(len - 1, nx, ny);
                }
            }
        }
    }

    return dp[len][i][j];
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2186.java

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

class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int N, M, K;
    static char[][] arr;
    static String end;
    static Integer[][][] dp;
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        initDP();
        fillDP();
    }

    public static void fillDP() {
        int len = end.length() - 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                result += dfs(len, i, j);
            }
        }
    }

    public static int dfs(int len, int i, int j) {
        if (dp[len][i][j] == null) {
            dp[len][i][j] = 0;

            if (arr[i][j] == end.charAt(len)) {
                for (int k = 1; k <= K; k++) {
                    for (int d = 0; d < dx.length; d++) {
                        int nx = i + dx[d] * k;
                        int ny = j + dy[d] * k;

                        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                        dp[len][i][j] += dfs(len - 1, nx, ny);
                    }
                }
            }
        }

        return dp[len][i][j];
    }

    public static void initDP() {
        char s = end.charAt(0);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == s) {
                    dp[0][i][j] = 1;
                }
                else {
                    dp[0][i][j] = 0;
                }
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new char[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        end = br.readLine();
        dp = new Integer[end.length()][N][M];

        br.close();
    }
}

---

4. 결과 및 회고

이번 문제는 정석적인 DP 풀이로 풀 수 있었다.