[Baekjoon] 백준 1520 내리막길 (G3 / DP) - Java

링크

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

1520번: 내리막 길

 

 

 

문제 해석

왼쪽 위 (0, 0)에서 시작하여, 오른쪽 아래(N-1, M-1)에 도착해야한다.

 

이때 이동하는 경로는 현재 있는 위치보다 낮은(숫자가 작은) 곳만 가능하다.

 

갈 수 있는 경로의 개수를 구하시오.

 

 

 

아이디어

갈 수 있는 모든 길을 찾아야하므로 dfs를 사용해야 합니다.

 

단 map의 크기가 500*500이므로 단순 dfs를 사용해서 탐색하기에는 시간초과가 날 가능성이 높습니다.

 

따라서 메모이제이션 기법을 사용하여 왔던 길을 저장한다면 해결가능합니다.

 

dp배열은 map과 동일한 크기를 가지며, 만약 목표지점을 찍고 돌아온 적이 있다면 찍고 돌아온 정보를 저장합니다.

dp[][]에 저장되는 값
-1 : 지나가지 않은 위치
0 : 지나간 위치이지만 도착점까지 갈 수 없는 길
자연수 : 해당 위치에서 도착점까지 갈 수 있는 길의 경우
  -> 시작점 : 시작점에서 도착점까지 갈 수 있는 모든 경우의 수를 저장함  

 

 

 

코드

import java.io.*;
import java.util.*;

public class 내리막길 {

	static int X;
	static int Y;
	static int[][] map;
	static int answer;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int[][] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		X = Integer.parseInt(st.nextToken());
		Y = Integer.parseInt(st.nextToken());

		map = new int[X][Y];
		dp = new int[X][Y];

		for (int i = 0; i < dp.length; i++) {
			Arrays.fill(dp[i], -1);
		}

		for (int i = 0; i < X; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < Y; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

//		print(map);

		// 완탐
//		answer = 0;
//		dfs(0, 0);
//		System.out.println(answer);

		// 메모이제이션 사용
		System.out.println(dfs2(0, 0));
	}

	private static int dfs2(int x, int y) {
		if (x == X - 1 && y == Y - 1) {
			answer++;
			return 1;
		}

		int answer = 0;

		if (dp[x][y] != -1) { // 지나간 적이 있는 길이라면
			return dp[x][y];
		}
		dp[x][y] = 0; // 지나왔음을 표기
		for (int d = 0; d < dx.length; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx >= 0 && nx < X & ny >= 0 && ny < Y && map[nx][ny] < map[x][y]) {
				answer += dfs2(nx, ny);
			}
		}

		dp[x][y] = answer;
		return dp[x][y];
	}

	private static void dfs(int x, int y) {
		if (x == X - 1 && y == Y - 1) {
			answer++;
			return;
		}

		for (int d = 0; d < dx.length; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx >= 0 && nx < X & ny >= 0 && ny < Y && map[nx][ny] < map[x][y]) {
				dfs(nx, ny);
			}
		}
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

 

 

 

발생한 문제 & 해결 방안

Arrays.fill()은 1차원 배열에서만 사용할 수 있다.

배열의 copy와 마찬가지로 for문을 사용하여 한줄씩 채워야 한다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice