BOJ G3 2186 문자판 JAVA

2186번: 문자판

---

문제 읽기

일단 문제를 처음 읽고서는 BFS로 풀었었다. 하지만 거의 바로 메모리 초과가 났었고! 맵의 크기는 작지만 k의 존재와 중복 방문이 가능하기 때문에 BFS 수행 시 큐가 터져버리는 것이었다. (어쩐지 골드3인데 너무 쉽게 풀려서 이상했다.) 그래서 DFS로 접근했다.

 

단순 DFS를 처음에 했는데, 아무래도 중복 방문이 가능하다보니 이번엔 시간 초과가 났었다. 질문 게시판을 조금 뒤져서 메모제이션을 사용한다는 방식을 알게 되었고, 이를 활용해서 문제를 해결했다.

---

문제 풀기

위에서 말했듯이 나는 DFS + 메모제이션(DP개념)을 사용하여 해당 문제를 해결했다. DFS 코드를 짜다 보면 감이 올 텐데, 중복 방문이 가능하다는 점 때문에 단순 DFS로 구현하면 시간이 오래 걸릴 수밖에 없다. 그래서 중복된 계산을 줄일 수 있는 메모제이션을 사용해야 해당 문제를 시간초과가 나지 않게 풀 수 있다.

 

즉, 한 지점에 대해 이미 계산된 것이라면 메모제이션 배열에서 계산된 값을 찾아 사용하고, DFS를 중복해서 수행하지 않는 게 핵심이다.

 

이를 위해서 memo 배열을 선언했다.

static int[][][] memo;
memo = new int[N][M][target.length()];
for (int i = 0; i < N; i++){
   for (int j = 0; j < M; j++){
       Arrays.fill(memo[i][j], -1);
   }
}

 

memo 배열을 전역으로 선언하고, main 내부에서 모두 -1로 초기화를 시켜주었다.

memo 배열의 역할

 

memo 배열은 입력 받는 맵의 모든 지점에 대해서 dfs를 수행하여 얻은 값을 저장해두는 배열이다. 3차원 배열인 이유는, 첫 번째와 두 번째는 맵의 각 위치를 나타내고, 마지막 인자는 찾아야 하는 타겟 문자열의 idx를 나타낸다. 즉, 맵에서 해당 위치에 있는 알파벳이, 타겟 문자열의 해당 idx와 같으면, dfs를 수행하고 그 값을 저장해두는 것이다.

-1로 초기화 한 이유

 

그렇다면 왜 -1로 초기화한 걸까?

-1로 초기화 하지 않는다면 그냥 0이라는 값이 들어갈 것이다. 그럼 0이라는 값은 다음의 두 가지 의미를 가진다.

1. 아직 방문하지 않은 위치이다.
2. 방문해서 DFS를 수행했지만, 타겟 문자열을 만들지 못했기 때문에 0이 저장되었다.

즉, -1로 초기화해주지 않으면 0은 위와 같은 두 가지 의미를 지니기 때문에 똑같은 DFS 계산을 또 수행할 가능성이 높아진다. 따라서 시간초과가 날 수 있다.

 

이렇게 -1로 초기화 한 것을 유의하면서, 다음과 같이 코드를 짜주면 된다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_2186_문자판 {
    static class Pos{
        int r, c;
        int depth;
        public Pos(int r, int c, int depth){
            this.r = r;
            this.c = c;
            this.depth = depth;
        }
    }
    static int N, M, K;
    static char[][] map;
    static String target;
    static int[][][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.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++){
            map[i] = in.readLine().toCharArray();
        }
        target = in.readLine();

        memo = new int[N][M][target.length()];
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                Arrays.fill(memo[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);
                }
            }
        }

        int sum = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (memo[i][j][0] != -1) sum += memo[i][j][0];
            }
        }
        System.out.println(sum);

    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    private static int dfs(int i, int j, int pos) {
        for (int k = 1; k <= K; k++){
            for (int di = 0; di < 4; di++){
                int nr = i + dr[di]*k;
                int nc = j + dc[di]*k;
                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                int nextPos = pos + 1;
                if (map[nr][nc] == target.charAt(nextPos)){
                    if (nextPos == target.length()-1) {
                        memo[nr][nc][nextPos] = 1;
                    }
                    else if (memo[nr][nc][nextPos] == -1){
                        memo[nr][nc][nextPos] = 0;
                        memo[nr][nc][nextPos] += dfs(nr, nc, nextPos);
                    }
                    if (memo[i][j][pos] == -1) memo[i][j][pos] = 0;
                    memo[i][j][pos] += memo[nr][nc][nextPos];
                }
            }
        }
        return memo[i][j][pos];
    }

}