[BOJ] 백준 2186 : 문자판 (java)

🧪 3109 빵집

---

난이도 : 🌟 골드 3
유형 : 그래프 탐색 (DFS)

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자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

 

첫째 줄에 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

 

🚧  주의할 점

---

1. 같은 칸을 여러번 방문할 수 있다는 조건을 아래와 같은 경우만 고려했다.

- (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
- (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)

 

하지만 이런 경우 뿐만이 아니라 입력값이 아래와 같을 때 (0, 0) (1, 0) (1, 1) (1, 0) (0, 0) (0, 1) 의 다시 되돌아가는 경로도 고려해야한다.

4 3 1
SAH
OSJ
SAK
OSC
SOSA

answer : 16

 

2. dfs를 활용하여 문제를 풀고 시간 초과가 발생했다. 시간을 단축시키기 위해 메모이제이션을 사용하여 문제를 풀어야한다.

 

🧐 핵심 로직

---

◈  `if (dp[x][y][now] != -1) return dp[x][y][now];` : 처음에 초기화 한 -1 값과 다르다면, 좌표 (x, y) 에 위치한 문자 이후로 경로를 만들어 본 적이 있기 때문에, 그 값을 가져다 쓴다.

 

◈  `if (now == target.length - 1) return dp[x][y][now] = 1;` : 타겟 문자열을 만들었으므로 가능한 경로가 된다. 따라서, 경로가 하나 추가됬음을 의미하도록 1을 리턴시킨다.

💻 최종 코드 (480 ms → DFS, 메모이제이션)

---

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

public class Main {

    static int n, m, k, cnt;
    static String targetWord;
    static int[][][] dp;
    static char[][] wordMap;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        cnt = 0;
        wordMap = new char[n][m];

        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            for (int j = 0; j < m; j++) {
                wordMap[i][j] = word.charAt(j);
            }
        }

        targetWord = br.readLine();

        dp = new int[n][m][targetWord.length()]; // 좌표 (i, j)에 영단어( target )의 k 번째 인덱스로 방문했을 시, 그 뒤로 만들어지는 경로들의 수

        for (int[][] outerArr : dp) {
            for (int[] innerArr : outerArr) {
                Arrays.fill(innerArr, -1); // 경로의 수 0과 초기화 값을 구분하기 위해 -1
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (wordMap[i][j] == targetWord.charAt(0)) {
                    cnt += dfs(i, j, 0);
                }
            }
        }

        System.out.println(cnt);

        br.close();
    }

    private static int dfs(int x, int y, int idx) {

        if (dp[x][y][idx] != -1) return dp[x][y][idx];
        if (idx == targetWord.length() - 1) return dp[x][y][idx] = 1; // 타겟 문자열이 만들어진 경우 마지막 경로는 1이 된다.

        dp[x][y][idx] = 0; // 뒤에 올 경로의 경우가 0이더라도 초기화를 -1로 했기 때문에 0을 넣어줘야 한다.

        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= k; j++) {
                int nx = x + dx[i] * j;
                int ny = y + dy[i] * j;

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                if (wordMap[nx][ny] == targetWord.charAt(idx + 1)) {
                    dp[x][y][idx] += dfs(nx, ny, idx + 1);
                }
            }
        }

        return dp[x][y][idx];
    }
}