백준 팰린드롬 경로(2172)

팰린드롬 경로

1. 힌트

1) $(u1, u2)$에서 시작해서 $(v1, v2)$에서 끝나는 팰린드롬 문자열 $S$를 생각해보자$(|S| = L)$, 경로가 어떻게 진행될진 모르겠지만 $S[1]$과 $S[L]$은 같아야 하고 시작과 끝을 한 칸씩 땡기면 $S[2]$와 $S[L - 1]$도 같아야 한다.

2) 경우의 수는 참조적 투명성을 만족하므로 DP로 해결할 수 있다. 필요한 인자는 팰린드롬의 시작 좌표와 끝좌표 그리고 팰린드롬의 길이이다. 공간 복잡도는 $20^5$이므로 가능하다.

3) 양 끝을 이동시키는 방법은 $8 \times 8$가지가 있으므로 이에 대해 모두 시도해준다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

팰린드롬?

팰린드롬은 재귀적이기 때문에 문자열의 양 끝 위치만 알고 있다면 재귀적으로 해결할 수 있을 것 같다.

2) 문제를 분해할 수 있을까?

$(u1, u2)$에서 시작해서 $(v1, v2)$에서 끝나는 길이가 $L$인 팰린드롬 경로 $S$를 생각해보자. $S[1]$과 $S[L]$은 같아야 하고 시작과 끝을 한 칸씩 땡기면 $S[2]$와 $S[L - 1]$도 같아야 한다. 이동을 하는 방법은 양 끝 각각 $8$가지씩 있으므로 경로의 길이가 $L$이 아닐 수도 있겠지만 이는 예외처리하고 $64$가지의 모든 경우를 시도해서 구할 수 있다.

3. 구현

public class Main {
	static int N; static int[][] S;
	static int[][][][][] cache;
	
	static final int[] dy = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static final int[] dx = { -1, 0, 1, -1, 1, -1, 0, 1 };
	
	static boolean inRange(int y, int x) { return 0 <= y && y < N && 0 <= x && x < N; }
	
	// (u1, u2)에서 시작해서 (v1, v2)에서 끝나는 길이 l의 팰린드롬 경로의 개수
	static int dp(int u1, int u2, int v1, int v2, int l) {
		if (l == 2) {
			for (int d = 0; d < 8; d++) {
				int ny = u1 + dy[d]; int nx = u2 + dx[d];
				if (inRange(ny, nx) && ny == v1 && nx == v2) return 1;
			}
			return 0;
		}
		if (l == 1) return u1 == v1 && u2 == v2 ? 1 : 0;
		if (cache[u1][u2][v1][v2][l] != -1) return cache[u1][u2][v1][v2][l];
		int sum = 0;
		for (int d1 = 0; d1 < 8; d1++) {
			for (int d2 = 0; d2 < 8; d2++) {
				int nu1 = u1 + dy[d1]; int nu2 = u2 + dx[d1];
				int nv1 = v1 + dy[d2]; int nv2 = v2 + dx[d2];
				if (!inRange(nu1, nu2) || !inRange(nv1, nv2) || S[nu1][nu2] != S[nv1][nv2]) continue;
				sum += dp(nu1, nu2, nv1, nv2, l - 2);
			}
		}
		return cache[u1][u2][v1][v2][l] = sum;
	}
	
	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()); S = new int[N][N];
		int L = Integer.parseInt(st.nextToken());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) S[i][j] = Integer.parseInt(st.nextToken());
		}
		cache = new int[N][N][N][N][L + 1];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					for (int l = 0; l < N; l++)
						Arrays.fill(cache[i][j][k][l], -1);
		int sum = 0;
		for (int u = 0; u < N * N; u++) {
			int u1 = u / N; int u2 = u % N;
			for (int v = 0; v < N * N; v++) {
				int v1 = v / N; int v2 = v % N;
				if (S[u1][u2] == S[v1][v2]) sum += dp(u1, u2, v1, v2, L);
			}
		}
		System.out.println(sum);
	}
	
}

1) 시간 복잡도

2) 테스트 케이스