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

문제명 : 문자열 지옥에 빠진 호석 

난이도 : 골드5 / 1초 / 512MB

 

문제 

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다.
• 하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

 

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

 

풀이

 

1) DFS 를 이용

2) HashMap에 값을 보관하여 문자열이 만들어질 때마다 값을 찾아, value에 +1

3) max_length 를 두어 dfs 종료지점을 만들었다. 

 

import java.io.*;
import java.util.*;
import java.util.Map.Entry;


public class Main {
	static int n, m, max_length=0;
	static char[][] map;
	static Map<String, Integer> hs = new HashMap<>();
	
	private static void dfs(int i, int j, String s) {
		
		if (hs.get(s) != null) { 
			hs.put(s, hs.get(s)+1);
		}
		if (s.length() == max_length) { /* dfs 종료 지점  -> 신이 좋아하는 문자열 중 가장 긴 문자열 길이를 중심으로 !*/
			return;
		}
		
		int[] dx = {-1,-1,-1,0,0,1,1,1}; 
		int[] dy = {-1,0,1,-1,1,-1,0,1};
		for (int k = 0; k < 8; k++) {
			int xx = i + dx[k];
			int yy = j + dy[k];
			
			/* 예외처리 */
			if (xx < 0) xx = n-1;
			if (xx >= n) xx = 0;
			if (yy < 0) yy = m-1;
			if (yy >= m) yy = 0;
			
			dfs(xx, yy, s+String.valueOf(map[xx][yy]));
		}
	}
	public static void main(String[] args) throws Exception {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		map = new char[n+1][m+1];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		
		String[] valueSet = new String[K]; //순서대로 입력하기 위함. 
		
		for (int i = 0; i < K; i++) {
			String s = br.readLine();
			hs.put(s, 0);
			valueSet[i] = s; //일반 배열에 값을 넣어주어 나중에 출력할 때 위함.
			max_length = Math.max(max_length, s.length());
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dfs(i,j,String.valueOf(map[i][j]));
			}
		}
		
		for (int i = 0; i < K; i++) {
			System.out.println(hs.get(valueSet[i]));
		}
		
	}
	
}