글 읽기 - java 시간초과가 어디서 나는 건가요?

idpresent 5년 전 0

7%정도에서 시간초과가 나는데 어느부분이 문제인가요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static int[][] arr;		
	static int n,m;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input[] = br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		m = Integer.parseInt(input[1]);
		
		arr = new int[n][m];
		int[][] visited = new int[n][m];
				
		for(int i=0;i<n;i++) {
			String tmp = br.readLine();
			for(int j=0;j<m;j++) {
				if(tmp.charAt(j)=='H')
					arr[i][j] = 0;
				else {
					arr[i][j] = tmp.charAt(j)-'0';
				}
			}
		}
		int cnt = 1;
		cnt = boardgame(0,0,cnt,visited);
		bw.write(Integer.toString(cnt));
		bw.close();
	}

	public static int boardgame(int i, int j, int cnt, int[][] visited) {
		if(i<0||j<0||i>n-1||j>m-1) {//박스 밖에 있을 때
			return cnt-1;
		}
		else {
			int num = arr[i][j];
			
			int[][] visit_copy = new int[n][m];
		    for (int a = 0; a < visited.length; a++) {
		        System.arraycopy(visited[a], 0, visit_copy[a], 0, visited[a].length);
		    }
			
			if(visit_copy[i][j]==1) {
				return -1;
			}
			visit_copy[i][j]=1;
			
			if(num==0)
				return cnt-1;
			
			int max = -1;
			int tmp;
			tmp = boardgame(i-num,j,cnt+1,visit_copy);
			if(tmp == -1)
				return -1;
			if(max<tmp)
				max = tmp;
			tmp = boardgame(i+num,j,cnt+1,visit_copy);
			if(tmp == -1)
				return -1;
			if(max<tmp)
				max = tmp;
			tmp = boardgame(i,j-num,cnt+1,visit_copy);
			if(tmp == -1)
				return -1;
			if(max<tmp)
				max = tmp;
			tmp = boardgame(i,j+num,cnt+1,visit_copy);
			if(tmp == -1)
				return -1;
			if(max<tmp)
				max = tmp;
			
			return max;
		}
	}
}

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

문제

문제

출처

ICPC

java 시간초과가 어디서 나는 건가요?

idpresent 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말