[Programmers] 보행자 천국 (Java)

1.  문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1832

2.  문제

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

• 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
• 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
• 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

3.  제한사항

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

입출력 예

4.  소스코드

class Solution {
    int MOD = 20170805;
	public int solution(int m, int n, int[][] cityMap) {
		if(m == 1 && n == 1) return 1;
		int[][][] dp = new int[m][n][2];
		for(int row = 1; row < m; row++) {
			if(cityMap[row][0] == 1) break;
			dp[row][0][1] = 1;
		}
		for(int col = 1; col < n; col++) {
			if(cityMap[0][col] == 1) break;
			dp[0][col][0] = 1;
		}
		for(int row = 1; row < m; row++) {
			for(int col = 1; col < n; col++) {
				if(cityMap[row][col] == 1) continue;
				dp[row][col][0] = cityMap[row][col - 1] == 2 ? dp[row][col - 1][0] % MOD : (dp[row][col - 1][0] + dp[row][col - 1][1]) % MOD;
				dp[row][col][1] = cityMap[row - 1][col] == 2 ? dp[row - 1][col][1] % MOD : (dp[row - 1][col][0] + dp[row - 1][col][1]) % MOD;
			}
		}
		return (dp[m - 1][n - 1][0] + dp[m - 1][n - 1][1]) % MOD;
	}
}

5. 접근

• 만약 m과 n이 모두 1이라면 시작점과 도착점이 같다는 뜻이므로 경우의 수가 1가지이기 때문에 1을 반환합니다.
• 주어진 cityMap과 같은 크기의 dp 배열에 각 위치까지 갈 수 있는 경로의 수를 적는데, 이 때 이동할 수 있는 방향이 오른쪽 또는 아래 방향 총 두 가지 방향이므로 각 방향 또한 나타내야 하기 때문에 dp 배열을 3차원으로 생성합니다.
• dp 배열에서 dp[0][col][0]일 때와 dp[row][0][1]일 때의 값들을 1로 초기화합니다.
  • 이 때, 각 방향에서 cityMap의 값이 1인 곳이 있는 경우, 해당 위치는 지나갈 수 없기 때문에 해당 위치 이후로는 모두 값을 0으로 초기화합니다.
  • 방향이 0일 때는 오른쪽을, 1일 때는 아래쪽을 의미합니다.
• (1, 1) 위치부터 각 위치를 돌면서(편의상 각 위치를 (row, col)이라고 하겠습니다.)
  • 만약 cityMap[row][col] 값이 1이면 지나갈 수 없는 곳이므로 아무 작업도 하지 않고 지나갑니다.
  • 만약 cityMap[row][col] 값이 2라면 왼쪽에서 왔다면 오른쪽 방향으로만, 위쪽에서 왔다면 아래쪽 방향으로만 지나갈 수 있기 때문에 방향이 0일 때의 값은 dp[row][col - 1][0] 값을, 방향이 1일 때의 값은 dp[row - 1][col][1] 값을 취합니다.
    • 문제에서 20170805으로 나눈 나머지 값을 반환하라고 하였기 때문에 각 값에서 20170805으로 나눈 나머지 값을 취합니다.
  • 만약 cityMap[row][col] 값이 0이라면 이전 위치의 방향에 대해 신경을 쓸 필요가 없기 때문에 방향이 0일 때의 값은 왼쪽 위치에서의 방향이 0일 때와 1일 때의 값의 합을 취하고 방향이 1일 때의 값은 위쪽 위치에서의 방향이 0일 때와 1일 때의 값의 합을 취합니다.
    • 이 값도 마찬가지로 20170805으로 나눈 나머지 값을 취합니다.
• 최종적으로 (m - 1, n - 1) 위치에서 방향이 0일 때와 방향이 1일 때의 값을 합하면 모든 경로의 수가 되기 때문에 이를 더한 후 20170805으로 나눈 나머지 값을 반환합니다.