백준 20166: 문자열 지옥에 빠진 호석(Java)

1 minute read

문제링크 : https://www.acmicpc.net/problem/20166

문제

img1

img2

img3

문제를 해결한 방법

저는 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);
		
	}

}

Categories:

Updated:

Comments