글 읽기 - dfs와 시간초과 관련 궁금해요!!

ingyo 7년 전 0

안녕하세요!

점프 문제를 푸는데 자꾸 시간초과가 나서 질문을 올립니다.

dfs로 경로를 탐색해서 목적지에 도달할때마다 하나씩 카운트하는식으로 짯는데, 이거보다 효율적이게 짤수있는건지 궁금합니다.

dp로만 풀리는걸까요 ㅠㅠ

import java.util.Scanner;


public class Jump {

	static int n; 
	static long cnt;
	static int[][] map;
	
	
	
	static void dfs(int a, int b){
		if (map[a][b] == 0)
			cnt++;
		
		int jump = map[a][b];
		
		if ((a+jump < n) && (map[a][b] != 0))
			dfs(a+jump,b);
		if ((b+jump < n) && (map[a][b] != 0))
			dfs(a,b+jump);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		map = new int[n][n];
		for (int i = 0 ; i < n ; i++){
			for (int j = 0 ; j < n ; j++){
				map[i][j] = in.nextInt();
			}
		}
		
		cnt = 0;
		dfs(0,0);
		System.out.println(cnt);
		
		
	}

}

sgchoi5 7년 전 1

N 이 100 정도 되기 때문에 dfs 로는 시간 초과 해결이 안 됩니다.

dfs 기본 코드에 dp 기법만 적용한다고 보시면 됩니다.

즉, dfs 수행 시에 i, j 지점을 여러 번 지나갈텐데, i, j 지점에 대한 가지수를 한 번 계산해두면 dfs 를 더 안하고 그냥 그 값을 return 한다고 보면 됩니다.

Code pattern (문제해결전략 참조) 입니다

ingyo 7년 전 1

아하!

우연히 블로그도 들어가봤는데 좋은글이 많네요 ㅎㅎ 감사합니다!

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

문제

문제

출처

ICPC

dfs와 시간초과 관련 궁금해요!!

ingyo 7년 전 0

sgchoi5 7년 전 1

ingyo 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말