[프로그래머스] 등굣길 :: C++, 효율성 통과하기, 코드

등굣길

문제

문제 설명

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

---

 

코드

#include <string>
#include <vector>

using namespace std;

bool isPuddles(int y, int x, vector<vector<int>> & pud){
    for(int i=0; i<pud.size(); i++){ // 10
        if(pud[i][0]==x+1 && pud[i][1]==y+1)
            return true;
    }
    return false;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    long long answer = 0;

    vector<vector<long long>> map(n, vector<long long>(m));
    for(int i=0; i<n; i++){ // 10^4
        for(int j=0; j<m; j++){
            if(i==0 && j==0){
                map[i][j] = 1;
                continue;
            }
            if(isPuddles(i, j, puddles)) { // 웅덩이가 있으면 0
                map[i][j] = 0;
                continue;
            }
            if(i>=1){ // 접하는 위쪽 구간이 있으면
                map[i][j]+=map[i-1][j]; // 위에서 온 수 더하기
                map[i][j]%=1000000007;
            }
            if(j>=1){ // 접하는 왼쪽 구간이 있으면
                map[i][j]+=map[i][j-1]; // 왼쪽에서 온 수 더하기
                map[i][j]%=1000000007;
            }
        }
    }
    answer = map[n-1][m-1];
    if(answer>=1000000007)
        answer %= 1000000007;
    return answer;
}

 

풀이

DP라기에는 너무 단순한, 그냥 배열을 이용한 덧셈 문제였다. 어릴 때부터 해오던 최단경로를 찾는 법을 이용하면 쉽게 풀 수 있다.

최단경로라는 사실을 줘놓고 또, 오른쪽과 아래로 제한을 걸어둬서 한 가지 방식으로만 풀 수 있게 해주었다.

방식은 (1,1)에서 1을 저장하면서 시작한 뒤, 웅덩이에는 0을 웅덩이가 아닌 곳에는 해당 좌표의 왼쪽과 위쪽의 수를 더해서 기재해주는 것이다.

 

그림처럼 색칠된 곳의 숫자는 왼쪽과 위에 기재된 수를 더해준 수이다.

웅덩이를 0으로 처리했으므로 웅덩이를 통해서 가는 경로는 세어지지 않는다.

 

채점결과

n이 10^4인데, O(n)으로 풀어서 시간은 적게 나왔다.

 

주의사항

코드 중간에 다음과 같은 식이 있는데,

map[i][j]%=1000000007;

수가 너무 커져서 long long 형으로 담긴 힘든 모양인지, answer에서 나머지를 구해주는 것만으로는 효율성 테스트에서 계속 실패가 나왔다.

그래서 코드 중간에 아예 나머지 연산을 넣어버리니까 그제서야 풀렸다... ㅂㄷ

효율성에서만 오류날 때는 자료형의 크기를 고려하자.