[BOJ] 2186 - 문자판 JAVA

www.acmicpc.net/problem/2186

2186번: 문자판

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

예제 입력 1

4 4 1

KAKT

XEAS

YRWU

ZBQP

BREAK

예제 출력 1

3

 

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static char[][] map = null;
    static int[][][] dp = null;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};
    static String target = null;
    static int n, m, k, ans;

    public static void dfs(int r, int c, int idx, int length) {
        if(idx == length - 1) {  // 마지막 idx까지 도착. 문자열 완성.
            dp[r][c][idx] = 1;
            return;
        }
        if(dp[r][c][idx] != -1) {  // 이미 방분한 곳이면 리턴하고 그 값 더함
            return;
        }
        dp[r][c][idx] = 0;  // 방문한 노드는 0으로 해줘야 함. -1값을 그대로 유지하면 나중에 값을 더할 때 문제가 생길 수 있다.

        for(int i = 1; i <= k; i++) {
            for(int j = 0; j < 4; j++) {  // k가 1씩 증가할 때마다 현재 위치에서 상하좌우 1칸씩 더 검사
                int nr = r + rArr[j] * i;
                int nc = c + cArr[j] * i;
                if(-1 < nr && nr < n && -1 < nc && nc < m) {  // n행 m열 범위 체크
                    if(map[nr][nc] == target.charAt(idx + 1)) {  // 다음 문자 일치하면 재귀
                        dfs(nr, nc, idx + 1, length);
                        dp[r][c][idx] += dp[nr][nc][idx + 1];
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        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로 초기화해야함
        for(int i = 0; i < n; i++) {  // 0으로 초기화하면
            for(int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == target.charAt(0)) {
                    dfs(i, j, 0, target.length());
                    ans += dp[i][j][0];
                }
            }
        }
        System.out.println(ans);
    }
}

 

너무너무너무너무너무 어려웠고 시간도 오래 걸렸다. 결국 구글링과 오픈카톡의 도움을 받았다.

 

일단 처음엔 문제를 잘못 이해했다. 같은 칸을 여러 번 방문할 수 "없다"인 줄 알았는데, "있다" 였다.

 

이는 무작정 중복조회가 가능하다는 의미가 아니다.

예를들어, ABABA 라는 문자열을 찾는다고 할 때, 하나의 좌표 (r, c)에 있는 A를 [0], [2], [4]에 모두 사용할 수 있다는 뜻이다.

즉, 다른 인덱스의 문자를 찾는 데에 한해서 중복조회를 허용한다는 것이다.

-> (근데 결국 그게 무작정 중복조회를 허용한다는 얘긴가..? 음..?)

-> (생각해보니 같은 인덱스에 대한 중복 조회를 허용하면 경우의 수가 무한하게 나오게 될 테니 이건 애초에 말이 안 되는 소리였다.)

 

 

비록 다른 인덱스에 한해서이긴 하지만 중복조회를 허용한다는 대목에서 브루트포스로는 절대 해결할 수 없다는 것을 눈치채야한다.

map의 크기는 최대 100*100으로 10,000이고 타겟 문자열의 최대 길이는 80. 대충 생각해봐도 브루트포스는 불가능하다.

 

다음 인덱스의 문자와 일치하는 좌표에 대해서만 재귀를 수행한다면 그래도 시간 안에 들어올 수 있지 않을까 하는 헛된 희망을 가지고 코드를 짰으나 어림도 없었다.

 

 

시간초과에서 빠져나오기 위해 DFS에 DP를 함께 사용해야한다.

DP문제에선 항상 그렇듯이 dp 배열에 무엇을 담을 것인지가 중요하다.

-> dp[r][c][idx] == (r, c)를 idx번째 인덱스로 사용할 수 있는 정답 경우의 수

 

이렇게하면 문제의 요구사항대로 같은 인덱스에 대해서는 중복조회를 막으면서 다른 인덱스에 대해서만 중복조회를 허용할 수 있게 된다.

 

DP의 초기값을 0으로 했다가 또 문제가 발생했다.

처음에는, 어차피 if(map[nr][nc] == target.charAt(idx + 1)) 을 사용해서 다음 인덱스의 문자가 일치하는 것에 대해서만 재귀호출을 실행하니까 초기화를 0으로 하더라도 별 문제가 없을 것이라고 생각했다.

 

그런데 별 문제가 있다.

 

예를 들어, 길이가 5인 문자열을 찾아야 할 때 길이 3까지만 일치하고 그 이후로는 일치하는 문자를 찾을 수 없다면? 

 

결국 dp[] = 0이 의미하는 바가 아래의 두 가지 경우를 모두 포함하게 되어 제대로 된 구분을 할 수 없게 된다.

1. 아직 방문하지 않음(= 초기값으로서의 의미)
2. 해당 경우에서 정답을 완성시킬 수 있는 경우의 수가 0개.

 

방문하지 않았으면 탐색을 진행하도록 하고, 해당 경우에서 정답을 완성시킬 수 없으면 더이상 탐색을 진행하지 않아야하는데, 초기값이 이렇게 중복적인 의미를 띄게 되면 메모이제이션이 제대로 작동하지 않게 되고.. 결과적으로 안 해도 될 탐색을 더 수행하게 돼서 시간초과가 나는 것이다.

 

모호성을 피하기 위해서 DP 초기값은 반드시 0이 아닌, "방문하지 않음" 만을 의미하도록 잡아야한다.

즉, 탐색을 진행하며 "절대로 발생할 수 없는 경우"로 초기값을 잡아줘야한다.

 

 

 

 

 

 

아, 어렵다...