[ 알고리즘 ] 코딩 - Programmers - 등굣길.java

---

문제 링크

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

코딩테스트 연습 - 등굣길

---

프로그래머스 - Level 3 - (자바) 등굣길 - 동적 계획법(DP)의 기초 1,1에서 m, n까지 가는 모든 경로 중 물이 있는 곳은 피해 가는 경로 제한 사항

---

 

로직

Step 01. 가장자리는 0으로 넣기위해 배열 크기 +1 해서 생성, 시작 위치를 1로 주어줌. Step 02. 만들어진 map에 물 웅덩이 위치 -1 표시 ( puddles[0][0] = x, puddles[0][1] = y 임을 조심하자 ) Step 03. 이동 방향이 오로지 오른쪽과 아래쪽이므로, 현재 위치에 위쪽 + 왼쪽의 값을 누적하며 갱신 ( DP ) Step 03-1. 왼쪽 혹은 위쪽에 웅덩이가 있는 경우 적절한 처리 Step 04. m,n 위치에 저장 된 값이 정답! 오답!

딱!! 하면 오잉???? 이렇게 된다?? 효율성이 시간초과가 아니라 실패다 '실. 패.' 그렇게 문제를 잘 살펴보면 아래 조건이 있다. Step 05. 위치의 모든 값이 갱신 및 누적 될 때 나머지 연산을 해주어야 한다.  Step 06. m,n위치의 값도 나머지 연산을 해주면 정답! 언제나 문제를 꼼꼼히 읽는 습관을 가지자!

---

코드

class Solution {
	    public int solution(int m, int n, int[][] puddles) {
	    	int[][] map = new int[n+1][m+1];
	    	map[0][1] = 1;
	    	
	    	int mod = 1000000007;
	    	
	    	for(int i = 0; i < puddles.length; i++) {
	    		int y = puddles[i][1]; // 1번 인덱스에 들어있는 것이 y
	    		int x = puddles[i][0];
	    		map[y][x] = -1;
	    	}
	    	
	    	for(int i = 1; i <= n; i++) {
	    		for(int j = 1; j <= m; j++) {
	    			if(map[i][j] == -1) continue; // 현재 위치 웅덩이
	    			if(map[i-1][j] == -1) { // 위쪽이 물웅덩이
	    				if(map[i][j-1] != -1) { // 왼쪽 웅덩이 아닌 경우, 왼쪽 값만 더해줌
	    					map[i][j] = map[i][j-1]%mod;
	    				} // else는 둘 다 웅덩이 이므로 넘어감
	    			} else { // 위쪽이 웅덩이가 아님
	    				if(map[i][j-1] != -1) { // 왼쪽 웅덩이 아닌 경우, 둘 다 웅덩이가 아니므로 더해줌
	    					map[i][j] = map[i-1][j]%mod + map[i][j-1]%mod;
	    				} else { // 왼쪽이 웅덩이. 위쪽 값만 내림
	    					map[i][j] = map[i-1][j]%mod;
	    				}
	    			}
	    		}
	    	}
	    	
	        int answer = map[n][m]%mod;
	        return answer;
	    }
	}