[프로그래머스] 등굣길 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

2. 입력

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

3. 예제

m	n	puddles	return
4	3	[[2, 2]]	4

4. 풀이

위 그림처럼 집에서 학교까지의 최단거리는 오른쪽과 아래쪽으로만 이동하여 곧바로 학교로 가는 경로가 된다.

 

지도의 특정 칸에 올 수 있는 이동 경로의 수를 2차원 배열 DP에 메모라이즈 하여 그다음 위치에 올 수 있는 이동 경로의 수를 구하는 방식으로 풀면 문제를 해결할 수 있습니다.

 

문제에서 이동은 오른쪽과 아래쪽으로만 이동이 가능하므로 지도의 특정 칸의 이동 경로의 수는 특정 칸의 위쪽 칸의 이동 경로의 수 + 왼쪽 칸의 이동 경로의 수가 된다.

 

위 식을 점화식으로 만들면 DP[i][j] = DP [i-1][j] + DP [i][j-1]이 된다.

 

m이 3이고 n이 2인 지도에서 우물이 없이 이동하는 경우의 수를 찾아보도록 하겠습니다.

 

위 그림의 A위치로 이동 가능한 경우의 수를 구하여보자 왼쪽 집에서 오는 경우 1개와 지도를 벗어난 A위 지점에서 오는 경우 1개이다. 그러나 위에서 오는 경우는 없으므로 A로 올 수 있는 경로의 수는 1개가 되다.

 

이번에는 B위치로 이동 가능한 경우의 수를 구하여보자 지도를 벗어난 B왼쪽 지점에서 오는 경우 1개와 위쪽 집에서 오는 경우 1개이다. 그러나 왼쪽에서 오는 경우는 없으므로 B로 올 수 있는 경로의 수는 1개가 된다.

 

마지막으로 C위치로 이동 가능한 경우의 수를 구하여보자 C왼쪽 지점에서 오는 경우 1개와 위쪽에서 오는 경우 1개이므로 2가지의 경우가 된다.

 

문제의 예제로 주어진 m이 4이고 n이 3인 지도에서 학교까지 가는 최단거리의 수는 총 10개가 된다.

계산을 쉽게 하기 위해 DP는 m, n 보다 1씩 큰 2차원 배열을 선언하고 1,1위치 부터 시작하도록 하였습니다.

 

지금까지 물에 잠긴 지역이 없는 경우 최단경로의 수를 찾았습니다.

이제 물에 잠긴 지역이 없는 풀이 과정에서 물에 잠긴 지역이 있다는 조건을 추가하여 보겠습니다.

 

위 그림 처럼 물에 잠긴 지역라는 것은 해당 위치로 올 수 있는 이동가능한 경우가 0이라는 것과 같은 것 이므로 물에 잠긴 지역이 없는 것 처럼 DP를 구성하다 물에 잠긴 지역이면 해당 DP의 값을 0으로 만들어 주면 됩니다.

 

5. 코드

전체 코드는 Git에 있습니다.

int[][] map = new int[n + 1][m + 1];

for (int[] puddle : puddles) map[puddle[1]][puddle[0]] = Integer.MAX_VALUE;

map[1][1] = 1;
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		if(map[i][j] == Integer.MAX_VALUE)
			map[i][j] = 0;
		else if (!(i == 1 && j == 1))
			map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007;
	}
}

return map[n][m];