백준 20166: 문자열 지옥에 빠진 호석(Java)
문제링크 : https://www.acmicpc.net/problem/20166
문제
문제를 해결한 방법
저는 DFS로 접근했습니다. 총 8개 방향을 시계방향으로 움직이는 dx
,dy
를 만들었고, 환형구조이기 때문에 조건문으로 처리했습니다. 해시맵에 신이 좋아하는 문자열을 입력 받으면서 DFS의 종료 조건을 위한 MAX_LENGTH를 구했습니다.
DFS에서 containsKey()
를 사용하여 count 해줬고, MAX_LENGTH에 도달하면 return 했습니다.
마지막 출력을 위해서 stringArray
에 신이 좋아하는 문자열을 입력 순으로 저장했습니다.
지금은 완전탐색으로도 풀렸지만, DFS 전에 신이 좋아하는 문자열을 입력 받지 않고, 입력 받으면서 count하는 방식이 더 좋은 것 같습니다…
소스 코드
package baek;
import java.io.*;
import java.util.*;
public class Main_20166_문자열지옥에빠진호석 {
static HashMap<String, Integer> map = new HashMap<>();
static int N, M, K, MAX_LENGTH;
static int[] dx = {-1,-1,0,1,1,1,0,-1}, dy = {0,1,1,1,0,-1,-1,-1}; // 시계방향
static char[][] hell;
public static void solve(int x, int y, int depth, String result) {
if(map.containsKey(result))
map.put(result, map.get(result) + 1);
if(depth == MAX_LENGTH)
return;
for(int dir=0;dir< dx.length;dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 0)
nx = N-1;
else if(nx >= N)
nx = 0;
if(ny < 0)
ny = M-1;
else if(ny >= M)
ny = 0;
solve(nx,ny, depth+1, result+hell[nx][ny]);
}
}
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());
K = Integer.parseInt(st.nextToken());
String[] stringArray = new String[K]; // 마지막 출력을 위한 Array
hell = new char[N][M];
map = new HashMap<>();
MAX_LENGTH = 0; // DFS의 종료를 위한 최대 depth
for(int i=0;i<N;i++) {
hell[i] = br.readLine().toCharArray();
}
for(int i=0;i<K;i++) {
String favoriteString = br.readLine();
MAX_LENGTH = Math.max(MAX_LENGTH, favoriteString.length());
map.put(favoriteString, 0);
stringArray[i] = favoriteString;
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
solve(i,j, 1, Character.toString(hell[i][j]));
}
}
StringBuilder sb = new StringBuilder();
for(String key: stringArray) {
sb.append(map.get(key)).append("\n");
}
System.out.println(sb);
}
}
Comments