안녕하세요. 오늘은 프로그래머스에서 동적계획법 문제 중 등굣길 문제 풀이를 진행해보겠습니다. 등굣길 문제 제목만 봤을 때, 길 찾기 문제가 아닐까 조심스럽게 예상해보며, 문제를 풀어보겠습니다.
프로그래머스 > 동적계획법 > 등굣길 문제 풀이
♥ 문제 정보
문제명: 등굣길
문제 난이도: Level 3
문제 푼 사람 수: 9549명
사용 가능 언어: 3개 (Java 사용)
♥ 문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
집부터 학교까지 갈 수 있는 최단 경로의 개수 구하기
Inputs
m: 학교가 있는 좌표의 x축 값
n: 학교가 있는 좌표의 y축 값
puddles: 물이 잠긴 지역의 좌표 리스트로 갈 수 없는 지점
Output: 집부터 학교까지 갈 수 있는 길에 대한 최단 경로의 개수
등굣길 문제 풀이에서 위의 문제 설명에서 나온 이동 경로는 오른쪽과 아래쪽으로만 움직일 수 있는 점을 꼭 참고해야합니다.
♥ 제한 사항
º 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. º m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다. º 물에 잠긴 지역은 0개 이상 10개 이하입니다. º 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
1 ≤ m, n ≤ 100
m과 n이 모두 1인 경우는 없다.
0 ≤ 물이 잠긴 지역(puddles의 길이) ≤ 10
집과 학교가 물에 잠길 수 없다.
♥ 입출력 예
m
n
puddies
return
4
3
[[2,2]]
4
♥ 입출력 예 설명
위의 이미지와 같이 등굣길 문제 풀이의 입출력 예는 최단 경로로 갈 수 있는 길은 총 4개입니다.
♥ 알고리즘 만들기
1. 집에서 학교 가는 길을 표시하는 지도 변수를 만든다. 2. 위 지도에 물 웅덩이를 표시한다. 3. 시작점 [0, 0]부터 지점까지 갈 수 있는 경우의 수 더해준다. 지점 별 합산 값이 1,000,000,007보다 클 경우 나눈 나머지 값으로 채운다. 4. 모든 지점의 경우의 수를 확인 후, 지도에서 학교 위치에 있는 값을 반환한다.
위 알고리즘은 초등학교 때 최단 경로의 수를 구하기 위해 썼던 것으로 기억하는 알고리즘입니다. 다시 추억 속에서 꺼내서 코드로 구현하려니 떠오르지 않아서 애를 먹었습니다. 그럼 위 알고리즘의 이해를 돕기위해 문제에 있는 예로 어떻게 지도에 값이 채워지는지 과정을 설명하겠습니다.
위의 이미지와 같이 현 지점에서 위와 왼쪽 지점의 값을 더해서 현 지점으로 갈 수 있는 최단 경로의 수를 계속 채워가는 과정을 통해 마지막 학교까지의 최단 경로의 수를 구할 수 있는 알고리즘입니다. 그럼 위 알고리즘을 통해 코드로 구현해보겠습니다.
♥ 코드 구현
class Solution {
public int solution(int m, int n, int[][] puddles) {
// 1. 집에서 학교 가는 길을 표시하는 지도 변수를 만든다.
int maps[][] = new int[m][n];
// 2. 위 지도에 물 웅덩이를 표시한다.
for(int[] puddle : puddles) {
maps[puddle[0]-1][puddle[1]-1] = -1;
}
maps[0][0] = 1;
for(int x = 0; x < m; x++) {
for(int y = 0; y < n; y++) {
if(maps[x][y] != -1) {
// 3. 시작점 [0, 0]부터 지점까지 갈 수 있는 경우의 수 더해준다.
if(x > 0 && maps[x - 1][y] != -1) {
maps[x][y] += maps[x - 1][y];
}
if(y > 0 && maps[x][y - 1] != -1) {
maps[x][y] += maps[x][y - 1];
}
// 지점 별 합산 값이 1,000,000,007보다 클 경우 나눈 나머지 값으로 채운다.
if(maps[x][y] > 1000000007) {
maps[x][y] %= 1000000007;
}
}
}
}
// 4. 모든 지점의 경우의 수를 확인 후, 지도에서 학교 위치에 있는 값을 반환한다.
return maps[m-1][n-1] % 1000000007;
}
}
♥ 채점 결과
프로그래머스에서 등굣길 문제 풀이 결과 정확성 테스트 케이스 10개와 효율성 테스트 케이스 10개 모두 통과하여 문제 풀이를 완료하였습니다.
댓글