[동적 계획법] 등굣길 - Java코드 ★★★ (설계가 어려움)

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

문제

 

 

설계

오른쪽, 아래로만 움직이면서 침수된 판을 제외하고 지나갈수 있는 경로중 최소값 경로의 갯수를 구하는 문제이다.

최단 경로를 구하라 했지만, 사실 어떻게 가도 경로값은 같을수 밖에 없다;;

 

포인트

경로를 구하는 법은 내머리로 나오지 않았고 한 블로그를 참고했다

M,N의 이차원배열을 선언하고, 경로값을 초기화해주되, 범람지역은 0으로 생각하고 대각선의 값을 더해가며

END까지의 경로값을 구해주면 된다.

 

(내 머리로 못풀것같은 문제를, 오랫동안 잡고있는다고 , 풀리지 않는다ㅠㅠ

위와같은 그림이 갑자기 머리에서 나오지 않으니, 사고 시간은 1-2시간을 넘기지 말고, 설계방법을 찾아봅시다.

이해하고 코드를 내가짜면서 내꺼로 만들고 기억하면 되죠 뭐)

 

 

풀이

	public int solution(int m, int n, int[][] puddles) {
		int [][] a = new int[n][m];
		// 웅덩이는 -1로 초기화
		a[0][0]=1;
		for(int[] x : puddles)
			a[x[1]-1][x[0]-1] = -1;
		// 초기 경로셋팅
		for(int i=1; i<m;i++) {
			if(a[0][i]==-1 || a[0][i-1]==0)
				a[0][i]=0;
			else
				a[0][i]=1;
		}
		for(int i=1; i<n;i++) {
			if(a[i][0]==-1 || a[i-1][0]==0)
				a[i][0]=0;
			else
				a[i][0]=1;
		}				
		
		// 경로 구하기
		for(int i=1;i<n;i++) 
			for(int j=1;j<m;j++) 
				a[i][j] = a[i][j]==-1 ? 0 : (a[i-1][j] + a[i][j-1])%1000000007;

		return a[n-1][m-1]%1000000007;
	}

 

초기 경로 셋팅에 중요한점은,

웅덩이를 먼저 -1로 기록해두고, 

초기 경로 셋팅시에 , 웅덩이가 존재하거나, 자신이 웅덩이인 경우 (-1) 를 확인하여 0으로 셋팅해야 한다는것이다.