등굣길

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 이하인 자연수입니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

---

풀이

 전체적인 코드의 풀이 알고리즘은, 어렸을 적 수학에서 배웠던 좌표 상에서 두 위치 간의 최단거리 경우의 수를 그림에 표시해서 구하는 방법을 사용한다. 예를 들어,

A
				B

라고 하는 테이블에서 A에서 B까지 이어지는 최단거리를 구해야 할 때, 우리는 A위치에서 우선 오른쪽 가는 경우 1가지와 아래로 내려가는 경우 1가지를 표시하고 이를 퍼져나가며 합쳐가는 형식으로 경우의 수를 구해간다.

 

A(1)	1
1
				B

 이 후 여기서 경우의 수는 아래와 오른쪽으로만 내려가며, 해당 좌표에 모이는 모든 경우의 수는 합해 나간다.

A(1)	1	1
1	2
1
				B

 이렇게 좌표를 채워나가며 B에 도달했을 때의 경우의 수의 총합이 바로 A에서 B까지 최단경로의 수가 된다.

A(1)	1	1	1	1
1	2	3	4	5
1	3	6	10	15
1	4	10	20	B(35)

 물론 확률과 통계 공식을 사용하여 최단경로의 수를 구할 수도 있지만, 이 경우 웅덩이의 위치를 고려해야되는 반면에 이러한 방식은 알고리즘도 매우 단순하고 웅덩이도 쉽게 고려하여 계산을 진행할 수 있다. 이를 이용하여 코드에 적용하면, 우선 행과 열의 크기를 받아 격자를 만들어내고, 웅덩이의 위치를 미리 -1의 값으로 표시한다음 집의 좌표(0, 0)에 경우의 수값 1을 넣고 계산을 반복하면 된다. 이를 코드로 적용하면 다음과 같다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> route;

    for (int i = 0; i < n; i++) {//격자 생성
        vector<int> temp(m, 0);
        route.push_back(temp);
    }
    route[0][0] = 1;//시작 위치 경우의 수 1 대입

    for (int i = 0; i < puddles.size(); i++) { //웅덩이 표시
        route[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
    }

    for (int i = 0; i < n; i++) {//행
        for (int j = 0; j < m; j++) {//열
            if (route[i][j] != -1) {//해당 위치가 웅덩이가 아니라면
                if (i > 0 && route[i - 1][j] != -1)//위쪽이 있고 웅덩이가 아니라면
                    route[i][j] += route[i - 1][j];
                if (j > 0 && route[i][j - 1] != -1)//왼쪽이 있고 웅덩이가 아니라면
                    route[i][j] += route[i][j - 1];

                route[i][j] = route[i][j] % 1000000007;//추가적인 연산 진행
            }
        }
    }
    
    return route[n - 1][m - 1]; //학교의 위치 값이 정답
}

 

---

결과