[문제 풀이] 백준 2186 문자판

안녕하세요

오늘의 문제는 https://www.acmicpc.net/problem/2186

문자판입니다. 

문제 들어가기 앞서 제가 고민한 조건부터 확실하게 정하고 가겠습니다

 

1. 한 점에서 K 만큼 상하좌우로 움직일 수 있습니다. (k가 5이면 위로 4칸 이동이 가능)

 

2. 경로의 순서가 다르다면 다른 경로로 취급합니다.

2 2 2

AA

AA

AA

그래프 1

그래프1 의 경우 답은 8입니다.

 

문제 

영어 대문자로 이뤄진 가로 세로가 <=100 인 2차원 배열에서 특정 단어를 만드는 경우의 수를 찾아 합니다. 

 

풀이

먼저 2차원 배열을 순회하며 시작이 가능한 부분을 찾았습니다. 

 

그리고 그 점에서 DFS를 통해 단어가 이뤄지는지 탐색을 시작하였습니다. 

 

중복되는 탐색을 없애주기 위해서 각 탐색의 결과 값을 저장하였습니다. 3차원 배열을 사용하여 문자가 가능한 한 좌표의 문자가 몇 번째로 사용되었을 때 가능 한 경로의 수를 저장해 주었습니다. 

 

+

- 결과 값을 저장하는 배열의 초기 값을 0으로 설정할 경우 시간초과가 나옵니다.

 혹시 꼭 그렇게 하고 싶다면 각 좌표의 방문 체크 수단을 하나 더 추가하셔야 합니다. 

 

- 비트 마스킹을 도입하고 싶었지만, r c의 크기, 특정 좌표 중복 가능하다는 점에서 적절하지 않습니다. 

 

코드

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

public class Num2186문자판 {
    static int r,c,k,ans;
    static String word;
    static char[][] map;
    static int[][][] dp;
    static int[] dx ={1,0,-1,0} , dy={0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new char[r][c];
        for(int i=0;i<r;i++){
            String input = br.readLine();
            map[i] = input.toCharArray();
        }
        word = br.readLine();
        dp = new int[r][c][81];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }
        for(int i =0;i<r;i++){
            for(int j=0;j<c;j++){
                if(map[i][j] == word.charAt(0)){
                    ans+= DFS(i,j,1);
                }
            }
        }
        System.out.println(ans);
    }
    public static int DFS(int nowR, int nowC, int cnt){
        if(cnt == word.length()){
//            System.out.println(1);
            dp[nowR][nowC][cnt] = 1;
            return 1;
        }
        if(dp[nowR][nowC][cnt] != -1) return dp[nowR][nowC][cnt];
        dp[nowR][nowC][cnt] = 0;
        for(int j=1;j<=k;j++){
            for(int i=0;i<4;i++){
                int nextR = nowR+dx[i]*j;
                int nextC = nowC+dy[i]*j;
                if(nextR<r&&nextR>=0&&nextC<c&&nextC>=0&& map[nextR][nextC] == word.charAt(cnt)){
                    dp[nowR][nowC][cnt] += DFS(nextR,nextC,cnt+1);
                }
            }
        }
        return dp[nowR][nowC][cnt];
    }
}