(JAVA) 백준 21317번 : 징검다리 건너기 -- [DFS]

https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

 

안녕하세요.

 

이 문제는 간단합니다.

 

 

DFS를 사용하여 

 

1) 작은 점프(1칸 이동)

2) 큰 점프(2칸 이동)

3) 매우 큰 점프(3칸 이동) -> 1번만 사용 가능

 

각각의 경우에 DFS로 재귀호출하면 됩니다.

 

 

그래서 

각 돌에서 작은점프, 큰점프하는 데 드는 에너지를 2차원 배열[n][2]로 저장해두고 (0: 작은점프 / 1: 큰점프)

DP 2차원배열[n][2]을 별도로 만들어 해당 돌에 도착했을 때의 에너지 최소 값을 저장해둡니다.

(0: K점프 안한경우 / 1: K점프 한경우) 

 

DP 초기값(0)인 경우만 구분해서 잘 넣어주시면 

DP[n][0]과 DP[n][1] 중 적은 값을 출력하면 끝납니다.

** 이 때, 초기값을 MAX_VALUE로 설정해둬도 됩니다.

 

 

 

감사합니다.

 

 

소스코드

---

 

	package dfsbfs;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 징검다리 건너기
	// DFS
	public class p21317 {
	static int[][] jumps;
	static int[][] dp;
	static int n, k;
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.valueOf(br.readLine());
	jumps = new int[n][2]; // index 0 : 작은점프, index 1 : 큰점프
	dp = new int[n][2]; // 0 : K점프 안한경우 1 : K점프한 경우
	for(int i = 0; i < n - 1; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int smallJump = Integer.valueOf(st.nextToken());
	int mediumJump = Integer.valueOf(st.nextToken());
	jumps[i][0] = smallJump;
	jumps[i][1] = mediumJump;
	}
	k = Integer.valueOf(br.readLine());
	dfs(0, 0, 0);
	int min = dp[n - 1][0] == 0 ? dp[n - 1][1] : (dp[n - 1][1] == 0 ? dp[n - 1][0] : Math.min(dp[n - 1][0], dp[n - 1][1]));
	System.out.println(min);
	}
	// hasBigJumped -> 0: 매우 큰 점프 사용X / 1: 매우 큰 점프 사용
	static void dfs(int stoneIndex, int energy, int hasBigJumped) {
	if(stoneIndex >= n) { // 돌밖으로 벗어나는거면 의미없음
	return;
	}
	// 최소 에너지를 찾아야 하기 때문에 현재 최소 에너지보다 크면 DFS할 필요가 없다.
	if(dp[stoneIndex][hasBigJumped] == 0) {
	dp[stoneIndex][hasBigJumped] = energy;
	}
	else {
	if(dp[stoneIndex][hasBigJumped] < energy) {
	return;
	}
	dp[stoneIndex][hasBigJumped] = energy;
	}
	// 1) 작은점프
	dfs(stoneIndex + 1, energy + jumps[stoneIndex][0], hasBigJumped);
	// 2) 큰점프
	dfs(stoneIndex + 2, energy + jumps[stoneIndex][1], hasBigJumped);
	// 3) 매우큰점프
	if(hasBigJumped == 0) {
	dfs(stoneIndex + 3, energy + k, 1);
	}
	}
	}

view raw p21317.java hosted with ❤ by GitHub