[Programmers/C++] 등굣길

 

💣 (출제자님의 의도가... 맞겠지요..?)

 

좌표와 배열은 반대로 봐야한다는 사실은 항상 인지하면서 조심스럽게 문제를 해결해 왔다.

처음부터 눈 부릅뜨고 "절대로" 여기서 실수 내지 말아야지!! 결심했다.

하지만 문제에서 주어지는 vector<vector<int>> puddles가 좌표 값이었을 줄이야..

심지어 앞 뒤가 같은 {2, 2}이어서 문제에 주어지는 그림을 보고도 알아차릴 수 없었단 게 함정이었다.

 

엄청난 실패 폭격 속에서 이유를 알아차렸을 땐..  🌠 🌠 🤯 🌠 🌠 🌠 🌠 🌠

 

(나 당황했니..)

 

 

문제

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

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

문제

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

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

 

제한 사항

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

길 찾는 방법은 어렵지 않아서 원리만 간단히 써봤다.

(아마 고등학생 때, "확률과 통계" 과목에 이런 문제를 푸는 방법을 배웠던 기억이 난다.)

 

규칙은 아래와 같다.

• 출발 지점부터 각각의 칸에 도착하는 방법에 대한 경우의 수로 칸을 채운다.
• 이동은 오른쪽이나 아래로만 이동할 수 있다.

 

일단 출발 지점부터 표시를 해봤다.

1이 써진 지점은 출발 지점에서 그 지점까지 가는 방법이 1가지임을 뜻한다.

 

 

 

그럼 연두색 칸에 들어갈 경우의 수는 몇일까?

"?"에 들어갈 값은?

 

 

 

그림으로 표현하면 아래 사진과 같다.

정답은 2 다!

 

나머지 칸도 채워보면 아래와 같다.

최단경로의 개수는 4

출발 지점에서 도착 지점까지 갈 수 있는 최단경로의 개수는 4이다.

 

 

 

예시처럼 간단한 문제면 상관없겠지만, 문제에서 최대 100X100의 격자 크기임을 명시해 주었기 때문에, 100X100 격자에서도 거뜬하게 값을 구할 수 있는 방법을 사용해야 한다.

 

 

잘 보면 규칙을 찾아볼 수 있다.

바로, 특정 지점의 바로 왼쪽  값과 위쪽 값을 더하면, 그 지점까지 갈 수 있는 최단 경로의 개수가 된다.

규칙

 

위의 규칙을 적용해 구하자

 

 

물 웅덩이는 "갈 수 없는 지점"이므로 경우의 수를 0으로 둔다.

 

이런 방법이면 100X100 크기도 문제없다.

 

 

이 원리를 이용해서 문제를 해결할 수 있다.

 

---

#include <vector>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    //.# dp를 0으로 초기화
    int dp[101][101] = {0};
    
    //.# 웅덩이 위치는 -1로 표시
    for (int i = 0; i < puddles.size(); ++i) {
        dp[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    //.# dp[1][1] = 1로 시작점 초기화
    dp[1][1] = 1;
    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < m + 1; ++j) {
            //.# 웅덩이 위치는 스킵
            if (dp[i][j] == -1) {
                continue;
            }
            
            int left = 0; int up = 0;
            
            if (dp[i - 1][j] != -1) {
                up = dp[i - 1][j];
            } 
            
            if (dp[i][j - 1] != -1) {
                left = dp[i][j - 1];
            } 
                
            dp[i][j] += (left + up) % 1000000007;
        }
    }
    
    return dp[n][m];
}

 

💀 효율성 테스트 실패

dp를 0으로 초기화하는 식을 for문을 이용해 초기화를 했더니 효율성 테스트 10에서 실패했다.

//.# dp를 0으로 초기화

/* 효율성 테스트 통과 ❌ */
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        dp[i][j] = 0;
    }
}

/* 효율성 테스트 통과 ⭕ */
int dp[101][101] = {0};

 

 

💀 인자로 주어지는 vector<vector<int>> puddles는 "좌표"

좌표(x, y)를 배열에 입력할 때는 arr[y][x] 를 사용한다.

 

인자로 주어지는 puddles는 웅덩이의 "좌표"를 나타낸다. 

따라서 dp배열에 웅덩이 위치를 저장할 때 주의해야 한다.

//.# 웅덩이 위치는 -1로 표시

/* ❌ */
for (int i = 0; i < puddles.size(); ++i) {
    dp[puddles[i][0][puddles[i][1]] = -1;
}

/* ⭕ */
for (int i = 0; i < puddles.size(); ++i) {
    dp[puddles[i][1]][puddles[i][0]] = -1;
}

 

---