PS/BOJ

2186(중요)

easy16 2022. 5. 1. 19:46

문자판 : https://www.acmicpc.net/problem/2186

 

메모이제이션 + dp + dfs가 혼합된 중요한 문제

 

문제를 이해하는 것 부터 시작하면, 다음과 같이 예제가 주어졌을 때

4 4 1
K[A][K]T
X[E]AS
Y[R]WU
Z[B]QP

 

BREAK //target인 BREAK를 만들기 위해 순회하면서 B를 찾은 뒤, 해당 위치에서 dfs를 호출한다.

K=1만큼 이동이 가능하므로, B로부터 4방향을 찾아보면

B->R->E->A-K를 조합할 수 있는 경우는 아래와 같이 3가지가 된다.

#case1
[K][A]K'T
 X [E]A'S
 Y [R]WU
 Z [B]QP
 

#case2
 K [A][K']T
 X [E] A'S
 Y [R] WU
 Z [B] QP

 

#case3
K A [K']T
X[E][A']S
Y[R] W U
Z[B] Q P

 

' 문자로 중복을 구분하고 경로를 살펴보면 E 및 A에서 경로가 2개로 나눠짐을 알 수 있다.

여기서 dp를 활용하게 된다. 중복처리를 하는 것이 어떻게 dp가 되는가를 따져보면,

 

B->R->E->A-K   == dp[kx][ky][4]=1; // case1가 완성되어 1이 리턴됨

B->R->E->A-K  

 dp[ax][ay][3] += dp[kx][ky][4]  

B->R->E->A-K'  == dp[k'x][k'y][4]=1; // case2가 완성되어 1이 리턴됨

B->R->E->A-K'  

 

B->R->E->A-K'  

dp[ex][ey][2] += dp[ax][ay][3] // A의 값이 E에 누적됨.

 

 

마지막으로 case 3가 A'를 통해 리턴되며 최종적으로 E는 3이 된다.

B->R->E->A'-K'  == dp[k'x][k'y][4]=1;

dp[a'x][a'y][3] += dp[k'x][k'y][4] // case2이 완성되며 리턴된 값이 A'에 누적됨.

dp[ex][ey][2] += dp[a'x][a'y][3] 

 

위와 같은 방식으로 최초에 호출된 B를 통해 누적된 모든 경우의 수의 합이 완성된다.

 

너무나 중요한 dp[x][y][index] 의 의미를 다시 한번 상기해보면,

x,y에 위치한 문자를 index번째로 거쳐서 target을 만들 수 있는 경우의 수 이다.

 

왜 index를 구분할 필요가 있는가?

ELEMENT 라는 target 이 있다고 가정하면, E가 3번 중복되는데 E에 대한 index가 없으면

몇번째에서 누적되어 와서 누적이 되었는지 총 몇번이 누적이 되었는지 구분이 되지 않는다.

 

index 덕분에 각 E의 위치에 따라 아래와 같이 구분하여 사용할 수 있게된다.

 

dp[x][y][0], 

dp[x][y][2],

dp[x][y][4],

 

 

 

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


public class Main {

	static boolean DBG = false;

	static int[] arr;
	static int N, M, K;
	static char[][] map;
	static String target;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int[][][] dp;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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++)
			map[i] = br.readLine().toCharArray();
		target = br.readLine();
		// System.out.println("target :" +target );
		// 좌표 x,y에 영단어 (target의 k번째 인덱스로 방문했을 시, 그 뒤로 만들어지는 경로들의 수를 의미
		// ex) break dp[1][2][3] 좌표 1,2에서 문자 A를 만나 만들 수 있는 경로의 수
		// 가능한 경로의 수가 0이 될 수 있으므로 -1로 초기화한다
		dp = new int[N][M][target.length()];
		for (int[][] arr : dp) {
			for (int[] ar : arr) {
				Arrays.fill(ar, -1);
			}

		}

		int answer = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == target.charAt(0))
					// 가능한 경로의 수를 누적
					answer += dfs(0, i, j);
			}
		}

		System.out.println(answer);
	}

	// 가능한 경로의 수를 리턴
	private static int dfs(int index, int x, int y) {
		if (dp[x][y][index] != -1) {
			if (DBG)
				System.out.printf("dupl : %d [%d %d] %c\n", index, x, y, map[x][y]);
			return dp[x][y][index];
		}
		// 0 1 2 3 4
		// BREAK : 마지막 인자의 index
		if (index == target.length() - 1) {
			if (DBG)
				System.out.printf("last : %d [%d %d] %c\n", index, x, y, map[x][y]);
			return dp[x][y][index] = 1;
		}

		//누적 경로를 계산하기 전, 값을 0으로 초기화
		dp[x][y][index] = 0;

		// 4-direction 마다 K번 검색
		for (int i = 0; i < 4; i++) {
			for (int k = 1; k <= K; k++) {
				int nx = x + dx[i] * k;
				int ny = y + dy[i] * k;

				if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
					// 예제의 경우 B로 시작했으므로 그 다음 문자인 R을 찾아야함.
					if (map[nx][ny] == target.charAt(index + 1)) {
						dp[x][y][index] += dfs(index + 1, nx, ny);
					}
				}
			}
		}

		if (DBG)
			System.out.printf("endf : %d [%d %d] %c value : %d \n", index, x, y, map[x][y], dp[x][y][index]);
		return dp[x][y][index];
	}
}

참조 : https://ddb8036631.github.io/boj/2186_%EB%AC%B8%EC%9E%90%ED%8C%90/

저작자표시