글 읽기 - 런타임에러 발생 질문드립니다.

barcelonamessi 7년 전 0

처음에는 dfs로 모든 경우(아래 오른쪽 왼쪽)를 가는 방향으로 생각했는데

다음 경로로 갈때 최대치로 경신하지 않는 경우는 탐색 안하는 것을 생각해서 추가했습니다.

또한 오른쪽이나 왼쪽으로 방향이 정해지면 다시 반대로 이동하지 않도록 cur_state상태를 추가하였습니다.

그런데도 런타임 에러가 나는것은 좌우로 계속 탐색을해서 스택 오버플로우가 나는 건지요??

아니면 다른 실수가 있었는지 궁금합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class A2169 {

	public static void main(String[] args) throws IOException{
		int N, M;
		int[][] map;
		int[][] visit;
		int[][] D;
		int count=0;
		int[] result=new int[1];
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token=new StringTokenizer(in.readLine());
		
		N=Integer.parseInt(token.nextToken());
		M=Integer.parseInt(token.nextToken());
		result[0]=Integer.MIN_VALUE;
		map=new int[N][M];
		visit=new int[N][M];
		D=new int[N][M];
		for(int i=0; i<N; i++){
			token=new StringTokenizer(in.readLine());
			
			for(int j=0; j<M; j++){
				map[i][j]=Integer.parseInt(token.nextToken());
				D[i][j]=Integer.MIN_VALUE;
			}
		}

		
		dfs(D,map, visit, N, M, 0, 0, N-1, M-1, 0, result, 0);
		System.out.println(result[0]);
	}
	public static void dfs(int[][] D, int[][] map, int[][]visit, int row, int col, int cur_x, int cur_y, int end_x, int end_y, int point, int[] result, int cur_state){
		//int result=point;
		
		System.out.println(cur_x + " "+cur_y+ "" +point+map[cur_x][cur_y]);
		if(D[cur_x][cur_y]>=point+map[cur_x][cur_y])
			return;
		D[cur_x][cur_y]=point+map[cur_x][cur_y];
		
		if(cur_x==end_x && cur_y==end_y){
			visit[cur_x][cur_y]=0;
			if(point+map[cur_x][cur_y]>result[0])
				result[0]=point+map[cur_x][cur_y];
				
			
		}
			
		//if(visit[cur_x][cur_y]==1)
		//	return 0;
		visit[cur_x][cur_y]=1;
		//오른쪽 왼쪽 아래 탐색해봄(안간부분 탐색)
		if(cur_state==0){
			if(cur_y+1<=col-1 && visit[cur_x][cur_y+1]==0){
				cur_state=1;
				if(D[cur_x][cur_y+1]<point+map[cur_x][cur_y]+map[cur_x][cur_y+1])
					dfs(D,map, visit, row, col, cur_x, cur_y+1, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
			if(cur_y-1>=0 && visit[cur_x][cur_y-1]==0){
				cur_state=-1;
				if(D[cur_x][cur_y-1]<point+map[cur_x][cur_y]+map[cur_x][cur_y-1])
				dfs(D,map, visit, row, col, cur_x, cur_y-1, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
			if(cur_x+1<=row-1 && visit[cur_x+1][cur_y]==0){
				cur_state=0;
				if(D[cur_x+1][cur_y]<point+map[cur_x][cur_y]+map[cur_x+1][cur_y])
					dfs(D,map, visit, row, col, cur_x+1, cur_y, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
		}else if(cur_state==1){//오른쪽만감
			if(cur_y+1<=col-1 && visit[cur_x][cur_y+1]==0){
				cur_state=1;
				if(D[cur_x][cur_y+1]<point+map[cur_x][cur_y]+map[cur_x][cur_y+1])
					dfs(D,map, visit, row, col, cur_x, cur_y+1, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
			
			if(cur_x+1<=row-1 && visit[cur_x+1][cur_y]==0){
				cur_state=0;
				if(D[cur_x+1][cur_y]<point+map[cur_x][cur_y]+map[cur_x+1][cur_y])
					dfs(D,map, visit, row, col, cur_x+1, cur_y, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
		}else{
			
			if(cur_y-1>=0 && visit[cur_x][cur_y-1]==0){
				cur_state=-1;
				if(D[cur_x][cur_y-1]<point+map[cur_x][cur_y]+map[cur_x][cur_y-1])
				dfs(D,map, visit, row, col, cur_x, cur_y-1, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
			if(cur_x+1<=row-1 && visit[cur_x+1][cur_y]==0){
				cur_state=0;
				if(D[cur_x+1][cur_y]<point+map[cur_x][cur_y]+map[cur_x+1][cur_y])
					dfs(D,map, visit, row, col, cur_x+1, cur_y, end_x, end_y, point+map[cur_x][cur_y], result, cur_state);
				
			}
		}
		
		visit[cur_x][cur_y]=0;
		
		
	}

}

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

문제

문제

출처

ICPC

런타임에러 발생 질문드립니다.

barcelonamessi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말