문제 이해

환형이라는 것은 아래 그림과 같다

글로 표현하자면 (1,1)에서 위로 가면 (N,1)이 되고, 왼쪽으로 가면 (1,M)이 되고 왼쪽 위 대각선 방향으로 가면 (N,M)이 되는 것이다.

그래프가 환형으로 이어져있다.
그리고 신이 좋아하는 문자열이 주어질 것이다.

이 때 상하좌우, 대각선 방향으로 1칸 씩 이동하며 신이 좋아하는 문자열을 만드려고 한다.
(지나왔던 구간을 재방문하는 것도 허락됨)

이 때 신이 좋아하는 문자열을 만드는 경우의 수를 구하는 문제이다.
(만약 방문 순서가 다르다면 2개의 경우의 수는 다른 것이다. (1,1) -> (1,2) 경우의 수와 (1,2) -> (1,1)의 경우의 수는 다른 경우로 간주한다)

---

문제 풀이

사실 Brute-force로 모든 경우의 수를 세 보는 것밖에 방법이 생각나지 않았다.
하지만 이 Brute-force를 어떻게 하면 조금 더 잘 할 수 있을지를 고민해야 하는 문제인 것 같다.

나는 arr[N][M]['문자열 길이']의 배열을 생성했다.

이후 문자열의 마지막 문자부터 Search하며 경우의 수를 셌다.

예를 들어 abc를 좋아하는 문자열으로 주어졌다고 가정하자.

먼저 arr[x][y] = c인 구간을 찾고, arr[x][y][3]에 1 값을 저장했다.

이후 arr[x][y] = b인 구간을 찾았다. 그런데 b이후에 c가 존재해야 한다.
따라서, arr[x][y][2]에 (x,y 기준) 상하좌우 및 대각선 방향으로 1칸 떨어져 있는 arr[x'][y'][3] 값을 모두 더해주었다.

a 또한 비슷한 과정을 거쳤다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int answer = 0;
	
	static int N,M;
	static char[][] arr;
	
	static void count(String point) {
    // point : 신이 좋아하는 문자열
    // 신이 존재하는 문자열을 만드는 경우의 수를 구하는 메서드
		int[][][] num_arr = new int[N][M][point.length()];
		int ans = 0;
		for(int c =point.length()-1;c>=0;c--) {
			char tgt = point.charAt(c);
			for(int i =0;i<N;i++) {
				for(int j =0;j<M;j++) {
					if(arr[i][j]==tgt) {
                    // 현재 확인하고 있는 문자열의 문자와 환형 배열에
                    // 존재하는 문자가 동일한 경우
                    
						if(c==point.length()-1) {
                        // 문자열의 마지막 부분이다.
                        // 마지막 부분은 배열 문자와 일치하기만 한다면 1로 
                        // 설정한다
							num_arr[i][j][c] = 1;
						}
						else {							
							int s_i = (i + 1)%N;
							int s_j = (j + 1)%M;
                            // s_i : x축 방향으로 1증가
                            // s_j : y축 방향으로 1증가
                            // %N, %M 연산을 통해 환형 적용
                            
							int e_i = i - 1;
							if(e_i==-1) e_i = N-1;
							int e_j = j-1;
							if(e_j == -1) e_j = M-1;
                            // e_i : x축 방향으로 1 감소
                            // e_j : y축 방향으로 1 감소
                            // -1값을 가질 때 N-1, M-1으로 치환하여 환형 적용
                            
							// 상하좌우 대각선 모든 경우의 수 더하기
							num_arr[i][j][c] = num_arr[i][s_j][c+1] 
                                              + num_arr[i][e_j][c+1]
                                              + num_arr[s_i][j][c+1] 
                                              + num_arr[e_i][j][c+1]
                                              + num_arr[s_i][s_j][c+1] 
                                              + num_arr[s_i][e_j][c+1] 
                                              + num_arr[e_i][s_j][c+1] 
                                              + num_arr[e_i][e_j][c+1];
						}
						
						
						if(c==0) {
							ans += num_arr[i][j][c];
						}
                        // c = 0이라는 것은 문자열 전체를 Search했다는 것이다
                        // 따라서 arr에 저장된 모든 값을 더해준다.
					}
				}
			}
		}
		sb.append(ans+"\n");
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		int K = sc.nextInt();
		
		arr = new char[N][M];
		
		for(int i =0;i<N;i++) {
			String str = sc.next();
			for(int j = 0;j< M;j++) {
				arr[i][j] = str.charAt(j);
			}
		}
		
		for(int k=0;k<K;k++) {
			String point = sc.next();
			
			count(point);
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 시간 초과 : arr를 활용하지 않고 정말로 Brute-force하게 문자열의 첫 부분부터 경우의 수를 셌을 때 시간 초과가 발생하였다.

• 부분 점수(12/16) 이유 : 신이 좋아하는 문자열의 길이가 1일 수도 있다. 즉, if(c==0) 무눅는 if~else 구문 밖에 존재해야 한다.
  하지만 코딩 실수로 if(c==0) 부분이 else 구문 안에 들어가서 부분 점수가 발생하였다.