보행자 천국(프로그래머스, Lv 3, Java)

1. 보행자 천국

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1832

코딩테스트 연습 - 보행자 천국 | 프로그래머스

알고리즘 설명:

왼쪽에서 오른쪽으로 가는 경우와 아래에서 위로 가는 경우, 이 두 가지 경우를 생각하고 풀면 된다.

• 오른쪽으로 가는 경우의 수를 넣을 배열과 위로 가는 경우의 수를 넣을 배열 선언
• 0,0은 cityMap 값이 0이기 때문에 이전 값들을 가져와서 더 해주어야 하지만 이전 인덱스는 마이너스인 상황
• outofBounds 예외처리가 되지 않기 위해 1 1에서 시작할 수 있도록 크기를 m+1, n+1로 준다.
• 조건 3가지
  • cityMap 값이 0인 경우:
    오른쪽과 위 모두 접근 가능하기 때문에 오른쪽 경우의 수는 i-1에서 오니까 right [i-1][j], 위 쪽 경우의 수는 j-1에서 오니까 up [i][j-1] -> 이 두 값의 합을 현재 인덱스의 right와 up에 넣어준다. -> 현재 인덱스까지 접근할 수 있는 경우의 수
  • cityMap 값이 1인 경우:
    접근 금지이므로 이전까지의 경우의 수와는 상관없이 현재 인덱스로 갈 수 있는 경우의 수는 0이다.
  • citMap 값이 2인 경우:
    오른쪽으면 오른쪽, 위쪽이면 위쪽 -> 한 가지 방법으로만 접근 가능하므로 오른쪽 경로 값은 왼쪽(i-1)의 right 값을, 위쪽 경로 값은 아래쪽(j-1)의 up값을 그대로 넣어주면 된다.
    • 값을 그대로 넣어주는 것은 현재 인덱스를 지날 때는 경로가 하나로 밖에 갈 수 없으므로 경우의 수가 그대로다. -> 이전 경로까지의 경우의 수를 가져온 이유
• 1,1의 right, up 값은 1로 시작해야한다.(1,1를 접근할 수 있는 것은 시작에서 1,1로 밖에 없다고 생각했다.)
• 반복문에서 인덱스의 값은 초기화 이후 한 번만 값이 변경된다. 하지만 1,1은 오른쪽 왼쪽도 가장자리 밖(1보다 작은 값)에서 값을 가져오기 때문에 1 값을 보존할 필요가 있다.
• cityMap에서 0,0 값은 항상 0이므로 cityMap이 0일 때 자기 자신을 추가로 더해주면 1,1의 1값이 보존된다. -> 오직 처음 시작만을 위한 처리...

막혔던 지점:

• 처음에는 오른쪽 왼쪽을 나누지 않고 cityMap값만 보고 조건식을 만들었다.
• 제대로된 방법을 사용하고도 1,1 처리를 하지 않아서 시간이 오래 걸림
• 마지막 return에서만 MOD를 나눠서 값이 틀림

코드(Java)

package coding;

public class WalkerHeaven {
	static int MOD = 20170805;

	public static int solution(int m, int n, int[][] cityMap) {

		int[][] rightMap = new int[m + 1][n + 1];
		int[][] upMap = new int[m + 1][n + 1];
		rightMap[1][1] = 1;
		upMap[1][1] = 1;

		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {

				int condition = cityMap[i - 1][j - 1];

				if (condition == 1) {
					rightMap[i][j] = 0;
					upMap[i][j] = 0;
				} else if (condition == 2) {
					upMap[i][j] = upMap[i][j - 1];
					rightMap[i][j] = rightMap[i - 1][j];
				} else {
					rightMap[i][j] += (upMap[i][j - 1] + rightMap[i - 1][j])%MOD;
					upMap[i][j] += (upMap[i][j - 1] + rightMap[i - 1][j])%MOD;
				}
			}

		}
		return (rightMap[m - 1][n] + upMap[m][n - 1])%MOD;
	}

	public static void main(String[] args) {
		int[][] map = { { 0, 2, 0, 0, 0, 2 }, { 0, 0, 2, 0, 1, 0 }, { 1, 0, 0, 2, 2, 0 } };
		System.out.println(solution(3, 6, map));

	}

}