[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)1520번, 내리막 길

문제 링크

1520번: 내리막 길

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

 

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

메모이제이션 DP[i][j]일 때 값은 i,j값을 시작점으로 제일 오른쪽 아래지점인 [N-1][M-1]이 조건에 만족하면서 도달할 수 있는 경우의 수를 저장하였습니다.

 

예제입력1에서 예를 들면

DP[3][3] = 15이며 DP[3][4]로 조건에 맞게 갈 수 있는 경우의 수는 DP[3][3]->DP[3][4]로 1개입니다.

 

DP[0][3] = 32이며 DP[3][4]로 조건에 맞게 갈 수 있는 경우의 수는

 

DP[0][3] -> DP[1][3] -> DP[2][3] -> DP[3][3] -> DP[3][4]

 

DP[0][3] -> DP[0][4] -> DP[1][4] -> DP[1][3] -> DP[2][3] -> DP[3][3] -> DP[3][4]

 

2개의 경우의 수가 나옵니다.

 

여기서 DP[1][3] -> .... -> DP[3][4]로 가능 경로가 동일하여 동일한 연산을 중복으로 진행할 수 있습니다.

 

중복을 방지하기 위해 DP[][]에 값이 존재하면 해당하는 i, j값은 탐색을 완료하였다고 판단할 수 있으므로

그 값을 더해주면 됩니다.

DP[1][3] = 1

 

DP[0][4] = 1

 

DP[0][3] = DP[1][3] + DP[0][4] = 2 처럼 구할 수 있습니다.

 

 

이제 조건에 대하여 말씀드리면

저는 조건을 만족하는 알고리즘을 작성하려고 DFS(깊이우선탐색)을 사용하였습니다.

 

지도는 배열의 형태로 나타내기 때문에 출발점인 (0,0)에서는 상하좌우만 이동할 수 있습니다.

dx[] = {-1, 1, 0 0}

dy[] = {0, 0, -1, 1}

DP[2][3]이면

상 : x = 2 - 1(dx[0]), y = 3 + 0(dy[0]) = [1][3]

하 : x = 2 + 1(dx[1]), y = 3 + 0(dy[1]) = [3][3]

좌 : x = 2 + 0(dx[2]), y = 3 - 1(dy[2]) = [2][2]

우 : x = 2 + 0(dx[3]), y = 3 + 1(dy[3]) = [2][4]

 

두 배열을 이용하여 각 기준마다 상하좌우로 이동하면서 깊이우선 탐색을 진행하도록 하였습니다.

 

탐색을 진행할 때 이동한 값이 현재 값보다 크거나 같으면 그 방향의 탐색을 종료하도록 하였습니다.

 

탐색이 [M-1][N-1]에 도착했을 때에는 하나의 경우의 수가 되는 것으로 1을 반환하였습니다.

 

이를 통해 DP[0][0]을 기준으로 깊이 우선 탐색을 진행하여 DP[][] 배열의 값을 얻었습니다.

 

결과적으로 DP[0][0]은 DP[M-1][N-1]에 도착할 수 있는 경우의 수를 모두 얻을 수 있기 때문으로

DP[0][0]을 결과로 출력하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. DP[][]의 값을 -1로 초기화해줍니다.

2. DP[0][0]을 기준으로 재귀를 통한 DFS(깊이 우선 탐색)을 진행하였습니다.

3. DP가 -1이 아니면 해당 DP값을 반환하고 아니면 DP[][]를 0으로 초기화 후 탐색을 진행합니다.

4. DP[0][0]을 결과로 출력합니다.

 

※ DP[][]를 -1로 초기화한 이유

[M-1][N-1]까지 도착할 수 없으면 경우의 수가 0이 저장됩니다.

int[] 배열에 초기값은 0이 저장되어 동일하므로 탐색할 때 탐색이 되었는데도 탐색이 되지 않았다고 판단하는 상황이 일어날 수 있습니다.

이 상황을 예방하기 위해  -1로 초기화하여 -1 값을 가지고 있다면 탐색이 진행되지 않았다고 판단하는 것입니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 지도 값들을 받고 board 배열을 초기화해주었습니다.
• 시작지점에서 목적지 가는 경우의 수 구하는 downhill 함수를 만들었습니다.
• BufferedWriter에 DP[0][0]의 값을을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• downhill은 DFS를 통해서 DP[0][0]부터 DP[M][N]까지 목적지 도달할 수 있는 경우의 수를 저장하였습니다.
• downhill은 위에 설명한 알고리즘 대로 DP와 board를 이용하여 목적지 도달 가능 경우의 수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] board;	//지도 값 저장 배열
	public static int[][] DP = new int[501][501];	//도착지점 갈 경우의 수 저장 배열
	public static int[] dx = {-1,1,0,0};		//상, 하, 좌, 우 x좌표 변경
	public static int[] dy = {0,0,-1,1};		//상, 하, 좌, 우 y좌표 변경
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----------입력값 저장 및 배열 초기화---------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int M = Integer.parseInt(st.nextToken());
    	int N = Integer.parseInt(st.nextToken());
    	board = new int[M][N];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<N;j++) {
    			board[i][j] = Integer.parseInt(st.nextToken());
    			DP[i][j] = -1;		//DP -1로 초기화
    		}
    	}
    	downhill(M, N, 0, 0);		//함수 실행
    	bw.write((DP[0][0]) + "\n");		//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //(0,0) -> (M-1,N-1) 경우의 수 구하는 함수
    public static int downhill(int M, int N, int curX, int curY) {
    	if(curX==M-1 && curY==N-1) {	//목적지 도착했을 때
    		return 1;
    	}
    	if(DP[curX][curY]!=-1)		//DP의 값이 -1이 아닌경우(탐색 했을 경우)
    		return DP[curX][curY];
    	
        //탐색 안했을 경우
    	int height = board[curX][curY];
    	DP[curX][curY] = 0;		//해당 DP값 0으로 초기화
    	for(int i=0;i<4;i++) {
    		int tempX = curX + dx[i];	//x값 상, 하, 좌, 우 이동
    		int tempY = curY + dy[i];	//y값 상, 하, 좌, 우 이동
    		if(tempX<0 || tempY<0 || tempX>=M || tempY>=N|| height<=board[tempX][tempY]) {
    			continue;		//배열의 값이 아니거나 조건에 불만족 할 경우
    		}else {
            		//조건에 만족한 경우 DFS 탐색
    			DP[curX][curY] += downhill(M, N, tempX, tempY);
    		}
    	}
    	return DP[curX][curY];
    }
}