오늘은 프로그래머스의 등굣길이라는 문제를 풀어 보았다.
문제 설명은 다음과 같다.
문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
- m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
- 물에 잠긴 지역은 0개 이상 10개 이하입니다.
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
위 문제는 집에서 학교로 가는 최단경로의 갯수를 구하는 문제이다.
문제를 읽고 곰곰히 풀이를 생각을 해보았다.
처음에는 재귀를 사용하여 dfs로 오른쪽과 아래로만 이동하면서 학교까지 도착하는 경로의 갯수를 세어 주었다.
이렇게 문제를 푸니 테스트 케이스와 정답률 테스트는 모두 정답을 받았지만 효율성에서 모두 시관초과를 받았다.
그렇게 다음으로 생각해본 풀이는 지도에서 맨 위칸과 맨 왼쪽 칸을 모두 1로 만들고 (1, 1) 경로에서 시작하여 왼쪽과 위를 더해서 (m, n)까지 계산하여 학교 위치에 남은 값을 구하는 방법이다.
이렇게 메모이제이션 기법을 사용하여 풀었더니 정답을 받을 수 있었다.
문제 풀이 코드는 다음과 같다.
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] map = new int[n][m];
for (int i = 0; i < puddles.length; i++) {
map[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
for (int i = 0; i < m; i++) {
if (map[0][i] == -1)
break;
map[0][i] = 1;
}
for (int i = 0; i < n; i++) {
if (map[i][0] == -1)
break;
map[i][0] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (map[i][j] == -1)
continue;
int num1 = map[i][j - 1] == -1 ? 0 : map[i][j - 1];
int num2 = map[i - 1][j] == -1 ? 0 : map[i - 1][j];
map[i][j] = (num1 + num2) % 1000000007;
}
}
return map[n - 1][m - 1];
}
}우선 먼저 지도를 표시하기 위한 map 2차원 배열을 m * n의 갯수로 생성을 해준다.
다음으로 물 웅덩이를 지도에 표시를 해준다.
그런다음 맨 왼쪽에 있는 모든 칸과 맨 위쪽에 있는 모든 칸을 1로 채운다.
여기서 주의할 점이 있는데 맨 위칸이나 맨 왼쪽칸에 1을 채워주다 물 웅덩이를 만나면 그 뒤로는 지나갈 수 없기 때문에 1로 채우지 않는다.
다음으로 (1, 1)부터 시작하여 위와 왼쪽에 있는 값을 더하여 해당 좌표에 값으로 써준다.
이 때 해당 좌표가 물 웅덩이라면 무시하고 왼쪽과 위가 물 웅덩이라면 0으로 계산한다.
이렇게 더하고 반복문을 다 돌려준 뒤 지도에 있는 학교 좌표의 값을 반환하게 되면 정답을 받을 수 있게 된다.
