글 읽기 - 시간초과 도와주세요.

shpre1236 7년 전 0

DFS와 BFS 둘다 짜보았는데 둘다 한 48% 쯤에서 시간초과가 납니다.

자바로 짜고 있는데 같은 문제 겪어보신 분, 문제점 좀 짚어주시면 감사하겠습니다.

FastScanner 부분은 BufferedReader를 이용해서 읽어오는데 공간관계상 뺐습니다.

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

public class p2186{
	static String target = null;
	static int N, M, K;
	static char[][] data;
	public static void main(String[] args){
		FastScanner sc = new FastScanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		
		String[] raw = new String[N];
		for(int i=0; i<N; i++){
			raw[i] = sc.nextLine();
		}
		
		data = new char[N][M];
		for(int i=0; i<N; i++)	for(int j=0; j<M; j++){
			data[i][j] = raw[i].charAt(j);
		}
		
		target = sc.nextLine();
		
		int result = 0;
		for(int i=0; i<N; i++)	for(int j=0; j<M; j++){
			if(data[i][j] == target.charAt(0))
				result += dfs(0, i, j);
		}
		
		System.out.println(result);
	}
	
	static int[][] step = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
	static int dfs(int n, int x, int y){
		int result = 0;
		if(n == target.length() - 1)	return 1;
		for(int i=0; i<4; i++){
			for(int k=1; k<=K; k++){
				if(x+k*step[i][0] < 0 || x+k*step[i][0] >= N 
						|| y+step[i][1]*k < 0 || y+step[i][1]*k >= M)
					break;
				
				if(data[x+k*step[i][0]][y+step[i][1]*k] == target.charAt(n+1))
					result += dfs(n+1, x+k*step[i][0], y+step[i][1]*k);
			}
		}
		return result;
	}

moonsoo5522 7년 전 1

이거 dp문제였던 걸로 기억합니다.

shpre1236 7년 전 0

답변감사합니다. 덕분에 잘 풀었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 도와주세요.

shpre1236 7년 전 0

moonsoo5522 7년 전 1

shpre1236 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말