[BOJ-1520]내리막길

 

 

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

1520번: 내리막 길

---

[풀이]

DP와 DFS를 활용한 문제이다.

 

도착점(M-1, N-1)에 도달할 때까지 경우의 수를 점화식으로 나타내면

DP[M-1][N-1]= DP[M-2][N-1]+ DP[M-1][N-2]

 

현위치가 (0,0) 인 시작점이라면 1을 리턴한다.

 

현위치가 (0,0)이 아닌 다른 점이라면

(1) 방문했다는 의미로, DP[y][x]=0 으로 한다.

(2) 현위치의 상/하/좌/우의 좌표(nexty, nextx)가 M행 N열 배열안의 원소인지 적절하지 먼저 확인하고(isRange 함수)

(3) 현위치의 상/하/좌/우가 현위치의 값보다 크다면 (arr[nexty][nextx] > arr[y][x])

DP[y][x]= (상)DP[y-1][x] + (하)DP[y+1][x] + (좌)DP[y][x-1] + (우)DP[y][x+1]

 

그러나 만약에 현위치(y,x)의 arr값보다 큰값을 갖는 상/하/좌/우 가 존재하지 않으면 어떻게할것인가?

그냥 현위치의 DP값을 리턴을 하면된다.

그러므로 return DP[y][x] 를 한다.

 

(4) 그래서 (3)에서 제시된 점화식을 수정하자면

DP[y][x]+= DFS(nexty, nextx)

 

---

[코드(.py)]

python의 경우 sys.setrecursionlimit(10**6)을 하지 않으면 런타임에러가 뜬다.

재귀할 때 유의하자.

import sys
sys.setrecursionlimit(10**6)

M,N =0,0
arr=None
dp=None

#현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global M,N
    if (y>=0 and y<M) and (x>=0 and x<N):
        return True
    return False

def dfs(y,x):
    global arr, dp
    # 현위치가 출발점인가?
    if (y==0 and x==0):
        return 1
    
    # 아직 방문하지 않은 상태인가?
    if dp[y][x]==-1:
        dp[y][x]=0 #현위치를 방문하고..
        
        for i in range(4):
            nexty=dy[i]+y
            nextx=dx[i]+x
            #현위치의 상/하/좌/우 가 적절한 범위에 있는가?
            if isRange(nexty, nextx):
                #현위치의 상/하/좌/우가 현위치의 값보다 큰가?
                if arr[nexty][nextx]>arr[y][x]:
                    dp[y][x]+=dfs(nexty, nextx)
                
    return dp[y][x]                    
                
    
def main():
    global M,N, arr, dp
    #M : 세로, N: 가로
    M,N = map(int, sys.stdin.readline().split())
    arr=[ list(map(int, sys.stdin.readline().split())) for _ in range(M)]
    dp=[ [-1]*N for _ in range(M)]
    result=dfs(M-1, N-1)
    print(result)
    
if __name__=='__main__':
    main()

 

---

[코드(.java)]

import java.util.Scanner;

public class Main{

	static int M,N;
	static int arr[][];
	static int dp[][];
	static int dy[]={-1,1,0,0};
	static int dx[]= {0,0,-1,1};
	
	public static void main(String[] args)
    {
		Scanner sc = new Scanner(System.in);
		M=sc.nextInt(); //세로크기
		N=sc.nextInt(); //가로크기
		arr=new int[M][N]; //arr선언
		dp=new int[M][N]; //dp선언
		
		for(int y=0; y<M; y++)
			for(int x=0; x<N; x++) 
            {
				arr[y][x]=sc.nextInt();
				dp[y][x]=-1;//-1로 초기화
			}		
		int result=dfs(M-1, N-1);
		System.out.println(result);
	}
	
	public static boolean isRange(int y, int x) {
		if((y>=0 && y<M)&&(x>=0 && x<N))
			return true;
		return false;
	}
	
	public static int dfs(int y, int x) {
		if(y==0 && x==0)
			return 1;
		
		//아직 방문하지 않은 상태
		if(dp[y][x]==-1) 
		{
			dp[y][x]=0;//현위치 방문
			
			//현위치 상/하/좌/우
			int nexty, nextx;
			for(int i=0; i<4; i++) 
			{
				nexty=y+dy[i];
				nextx=x+dx[i];
				if(isRange(nexty, nextx))
				{
					if(arr[nexty][nextx]>arr[y][x])
						dp[y][x]+=dfs(nexty,nextx);
				}
			}	
		}
		return dp[y][x];
	}
}