[자바] 백준 2418 - 단어 격자 (java)

목차

문제 : boj2418

 

 

필요 알고리즘

• DP (동적 계획법)
  
  • BFS 같은걸론 시간초과가 나게된다. 동적 계획법으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  '각 칸은 중복되게 사용해도 된다.' 부분이 문제인데, 이 부분때문에 BFS나 DFS로 진행 시 중복체크를 못하므로 시간복잡도가 저 멀리 가버리게 된다. 게다가 경우의 수의 경우 최대 10^18 이라고 했으므로, 따로 시간복잡도를 계산해보지 않아도 10^18번 찾는건 불가함을 알 수 있다.

 

  DP로 접근하면 생각보다 쉽게 풀 수 있다.

dp[a][b][c]를 (a, b) 칸에서 입력된 문자 중 c번 인덱스 문자까지 읽는 경우의 수라고 정의해보자.

이 경우 dp[a][b][c]는 c번 인덱스 문자가 'X'이고, c-1번 인덱스 문자가 'Y'라고 하면 (a,b)칸에 'X'가 존재할 경우 그 주변 8칸에 'Y'가 존재할 경우 그 경우의수를 더해주면 된다. 예를들어 (a-1, b-1)이 'Y'였다면 dp[a][b][c] += dp[a-1][b-1][c-1]이 된다.

 

  예제 입력 1의 경우를 보자.

3 4 5
ERAT
ATSR
AUTU
TARTU

dp[a][b][0] 부터 dp[a][b][5]를 dp[a][b] 까지만 나타내보면 다음과 같다. 각 칸의 문자는 입력으로 줄어졌던 격자의 문자이고, 숫자는 dp 배열에 담긴 경우의 수를 나타낸다. 다만 회색 숫자는 바로 직전(c-1)의 숫자를 알아보기 편하게 적어둔 것이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int len = Integer.parseInt(st.nextToken());

        char[][] arr = new char[r][c];
        for (int i = 0; i < r; i++) {
            String cur = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = cur.charAt(j);
            }
        }

        String word = br.readLine();
        long[][][] dp = new long[r][c][len];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == word.charAt(0))
                    dp[i][j][0] = 1;
            }
        }

        long answer = 0;
        for (int k = 1; k < len; k++) {
            char cur = word.charAt(k);
            char bf = word.charAt(k-1);

            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (arr[i][j] != cur) continue;

                    for (int dr = -1; dr <= 1; dr++) {
                        for (int dc = -1; dc <= 1; dc++) {
                            if (dr==0 && dc==0) continue;
                            int nr = i+dr;
                            int nc = j+dc;
                            if (nr<0||nr>=r||nc<0||nc>=c||arr[nr][nc]!=bf) continue;

                            dp[i][j][k] += dp[nr][nc][k-1];
                        }
                    }

                    if (k == len-1) answer += dp[i][j][k];
                }
            }
        }

        System.out.println(answer);
    }
}