[백준] 문자열 지옥에 빠진 호석 20166 [JAVA]

| Link

www.acmicpc.net/problem/20166

20166번: 문자열 지옥에 빠진 호석

---

| 풀이

1.  DP를 처음 적용해본 문제이다. ㅎㅎ 
2.  c->a->b의 개수를 구할 때, 색칠한 a로 부터 갈 수 있는 b의 길은 2가지로 정해져있다.
3. 따라서, a에서 또 dfs 를 통해 탐색할 필요가 없다는 것을 깨달았다. ==> a로부터의 가짓수가 많아지면 낭비 심해짐
4. 그러므로 DP를 적용하기로 생각했다.
5. 어떻게 적용할 수 있을까? 문자열의 끝부분 부터 탐색하며, 문자열의 첫 부분에는 해당 값들을 모두 더해주면 된다.

• DP를 3차원 배열로 만들어서 신이 좋아하는 문자열의 맨 끝부분 부터 시작해서 
• 도착할 수 있는 경우의 수를 저장해두는 방법
• DP[r][c][idx-1] += DP[nr][nc][idx];

---

| 어려웠던 점

• 처음엔 DFS로 풀었는데 시간초과 뜬다. 
• 틀린 코드 ↓

package 알고리즘스터디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 문자열지옥에빠진호석_20166 {

	// 8방 서치
	static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1};
	static char[][] map;
	static int[] answer ;
	static int N, M, K, size;
	static Queue<Str> q ;
	private static class Str{
		int r,c;
		int length;
		Str( int r,int c, int length){
			this.r =  r;
			this.c = c;
			this.length = length;
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken()); // 행
		M = Integer.parseInt(st.nextToken()); // 열 
		K = Integer.parseInt(st.nextToken()); // 신이 좋아하는 문자열 개수
		answer = new int[K];
		
		map = new char[N][M];
		for( int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			map[i] = st.nextToken().toCharArray();
		} // input
		
		for( int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine()," ");
			String target = st.nextToken();
			size = target.length();
			q = new LinkedList<>();
			for( int r= 0; r<N; r++) {
				for( int c =0; c<M; c++) {
					// 일단 시작점 같은 곳 찾고
					if( map[r][c] == target.charAt(0)) {
						//dfs(r,c,1,i, target);
						q.add(new Str(r,c,1));
						bfs(r,c,target, i);
					}
				}
			}
		}
		for( int output : answer ) {
			System.out.println(output);
		}
	}
	private static void bfs(int r, int c, String target, int idx ) {
		
		while( !q.isEmpty()) {
			
			Str cur = q.poll();
			
			// 다 찾았으면
			if ( cur.length == size ) {
				answer[idx] ++;
				continue;
			}
			
			for( int d =0; d<8; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];
				
				nr = updateR(nr);
				nc = updateC(nc);
				
				if ( map[nr][nc] == target.charAt( cur.length  ) ) {
					// 해당 지점에서 
					q.add(new Str(nr,nc, cur.length+1));
				}
				
			}
			
		}
		
	}
	
	/*
	 * idx : depth = 각 문자
	 * number : 신이 좋아하는 문자열의 각 번호 - 답의 인덱스
	 * target : 찾으려는 문자열
	 */
	private static void dfs(int r, int c, int idx, int number, String target) {
		if( idx == size ) {
			// 끝 문자도 같다면?
			if( map[r][c] == target.charAt(idx-1)) {
				answer[number] ++;
			}
			return;
		}
		
		// 8방 서치 하면서
		for( int d=0; d<8; d++) {
			
			int nr = r+dr[d];
			int nc = c+dc[d];
			
			nr = updateR(nr);
			nc = updateC(nc);
			
			if ( map[nr][nc] == target.charAt(idx) ) {
				// 해당 지점에서 
				dfs( nr,nc,idx+1, number, target);
			}			
		}				
	}
	private static int updateR(int r) {
		
		if ( r >= N ) return 0;
		else if ( r < 0 ) return N-1;
		
		return r;
	}
	private static int updateC(int c) {
		
		if ( c>= M ) return 0;
		else if ( c < 0 ) return M-1;
		
		return c;
	}
}

---

| 코드

package 알고리즘스터디;

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

public class 문자열지옥에빠진호석_v2_20167 {

	// 8방 서치
	static int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static char[][] map;
	static int[][][] DP;
	static int[] answer;
	static int N, M, K, size;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken()); // 행
		M = Integer.parseInt(st.nextToken()); // 열
		K = Integer.parseInt(st.nextToken()); // 신이 좋아하는 문자열 개수
		answer = new int[K];
		int idx =0;
		map = new char[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			map[i] = st.nextToken().toCharArray();
		} // input

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			String target = st.nextToken();
			size = target.length();
			DP = new int[N][M][size]; // 최대 문자열의 길이 5개니까.
			
			for (int s = size - 1; s >= 0; s--) {
				for (int r = 0; r < N; r++) {
					for (int c = 0; c < M; c++) {
						// 일단 시작점 같은 곳 찾고
						if (map[r][c] == target.charAt(s)) {
							// dfs(r, c, s + 1, i, target, r, c);
							update(r, c, s + 1, target);
							
							// target 문자열의 처음 이라면
							if ( s== 0 ) {
								answer[idx] += DP[r][c][s];
							}
								
						}
					}
				}
			} // update
			idx++;
			
			
		} // input

		for (int output : answer) {
			System.out.println(output);
		} // answer
	}

	private static void update(int r, int c, int idx, String target) {
		if (idx == size) {
			DP[r][c][idx-1]++;
			return;
		}

		// 8방 서치 하면서
		for (int d = 0; d < 8; d++) {

			int nr = r + dr[d];
			int nc = c + dc[d];

			nr = updateR(nr);
			nc = updateC(nc);

			if (map[nr][nc] == target.charAt(idx)) {
				DP[r][c][idx-1] += DP[nr][nc][idx];
			}

		}
	}

	private static int updateR(int r) {

		if (r >= N)
			return 0;
		else if (r < 0)
			return N - 1;

		return r;
	}

	private static int updateC(int c) {

		if (c >= M)
			return 0;
		else if (c < 0)
			return M - 1;

		return c;
	}

}

---

| 보완할 점

• HashMap으로도 풀 수 있는 것 같다. HashMap 방법에 대해 알아보고 수정하기.

---