백준 1520. 내리막 길

Seolang2·2023년 4월 10일
0

Algorithm

목록 보기
2/2

[문제] https://www.acmicpc.net/problem/1520

[풀이까지의 과정]

처음엔 단순 DFS만으로 풀릴 것이라 생각하여 4방 탐색과 visit을 이용해 구현하였는데, 약 13% 부근에서 시간초과가 발생했다.

백트래킹을 딱히 해주지 않았기에 가지치기 문제인가 고민했지만, 현재 위치보다 낮은 다음위치를 찾는 조건 이외의 가지치기를 할 조건이 떠오르지 않았다.

[Top-down 방식의 DP 구현]

결과적으로 이 문제는 DP를 사용해 해결할 수 있었다.
처음에 DP로 풀 수 있는가 고민했을 때, 위에서 아래로 순차적으로 값이 쌓이는게 아닌, 다른 경로를 통해 위쪽으로 다시 돌아올 수 있어 불가능하다 생각했다. 다만 이는 Buttom-up 방식일 때 불가능한 경우이고, Top-down 방식으로 도착지로부터 다시 돌아오며 진행했던 경로의 도달가능성을 쌓아나갈 수 있었다.

package day0410;

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

/*
 *  Top-down 방식의 DP 풀이
 *  
 */

public class acmicpc1520_내리막길 {
	
	static int M, N, answer;
	static int[][] map, dp;
	static int[] dr = {0, 1, 0, -1};
	static int[] dc = {1, 0, -1, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[M][N];
		dp = new int[M][N];
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
			}
		} // end input
		
		System.out.println(DFS(0, 0));
	}
	
	static int DFS(int r, int c) {
		if (r == M-1 && c == N-1) {
			return 1;
		}
		
		/*
		 * dp 초기값이 0이 아닌 -1인 이유
		 * 
		 * 만약 목표지점까지 도달하지 못한다면 0이 반환될텐데 이를 차후 DFS가 다시 방문했을때
		 * 아직 방문하지 않은 점인지, 가봤는데 경로가 없는 점인지 구분을 할 수 없어
		 * 다시 DFS를 재 수행하게 된다.
		 * 
		 */
		if (dp[r][c] != -1) return dp[r][c];
		
		dp[r][c] = 0;
		
		for(int dir=0; dir<4; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			
			if (isValid(nr, nc) && map[r][c] > map[nr][nc]) {
				dp[r][c] += DFS(nr, nc);
			}
		}
		
		return dp[r][c];
	}
	
	static boolean isValid(int r, int c) {
		return 0 <= r && r < M && 0 <= c && c < N;
	}
	
	static void print() {
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
	}
}

[후기]

알고리즘 문제를 풀면서 Top-down 방식의 DP를 구현해본건 처음이었다. 기존에는 for문을 사용한 Buttom-up 방식만 사용했어서, DP로는 풀이가 불가능하다 생각했는데 아니었다. Top-down 방식의 값 누적 방식을 좀 더 정리해봐야겠다.

profile
개발자 전직 일대기

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN