등굣길

문제 설명

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

 

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

---

문제 해설

DFS로도 DP로도 해결되는 문제이다. 여기서는 제한사항이 우측과 밑으로만 움직일 수 있기 때문에 DP형태로 푸는것 이 더 효율적이다.

 

중간에 가지 못하는 길이 있을 경우, DP의 연산알고리즘이 더하지 못하도록 예외처리 해야한다.

 

그리고 맨 마지막의 값을 호출하면 해결되는 문제

 

A*알고리즘을 이해하고 있다면 쉽게 풀 수 있는 문제이다.

것 참 이해하기 힘든것 이 가는 과정을 알아내는 것 이 더 중요할텐데 왜 짧은 길이 있다는 사실만 알아내려고 하는건지 모르겠다.

---

첫 시도

#include <string>
#include <vector>
#include <set>

using namespace std;
set<int> moveCount;

void Move(vector<int> nowpos, vector<vector<int>> Map, const vector<int>& target, int count = 0) {
    vector<vector<int>> NowMap = Map;
    NowMap[nowpos[0]][nowpos[1]] = 1;

    if (nowpos == target) {
        moveCount.insert(count-1);
        return;
    }

    if (nowpos[0] + 1 < Map.size() &&
        Map[nowpos[0] + 1][nowpos[1]] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[0]++;
        Move(nextpos, NowMap, target, ++count);
    }

    if (nowpos[1] + 1 < Map[0].size() &&
        Map[nowpos[0]][nowpos[1] + 1] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[1]++;
        Move(nextpos, NowMap, target, ++count);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> Map(m);
    for (auto& def : Map)
        def = vector<int>(n);
    for (auto& def : puddles)
        Map[def[0] - 1][def[1] - 1] = 1;

    Move(vector<int>{0, 0}, Map, vector<int>{m - 1, n - 1});
    return *moveCount.begin();
}

실패

대충 제귀로 짜봤는데 실패했다. 아마 제귀순환중 오류가 있기 때문인거 같다. 시간초과도 몃개 생겼으니, 좀더 효율적으로 짜야 할것같다.

---

두 번째 시도

#include <string>
#include <vector>
#include <map>

using namespace std;

map<int, int> moveCount;

void Move(vector<int> nowpos, vector<vector<int>> Map, const vector<int>& target, int count = 0) {
    vector<vector<int>> NowMap = Map;
    NowMap[nowpos[0]][nowpos[1]] = 1;

    if (nowpos == target) {
        moveCount[count]++;
        return;
    }

    if (nowpos[0] + 1 < Map.size() &&
        Map[nowpos[0] + 1][nowpos[1]] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[0]++;
        Move(nextpos, NowMap, target, count+1);
    }

    if (nowpos[1] + 1 < Map[0].size() &&
        Map[nowpos[0]][nowpos[1] + 1] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[1]++;
        Move(nextpos, NowMap, target, count+1);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> Map(m);
    for (auto& def : Map)
        def = vector<int>(n);
    for (auto& def : puddles)
        Map[def[0] - 1][def[1] - 1] = 1;
    
    Move(vector<int>{0, 0}, Map, vector<int>{m - 1, n - 1});
    
    return moveCount.begin()->second % 1000000007;
}

 

실패

생각해보니 map으로 count를 세야 하는데 set으로 이동겟수를 넣고있었음, map으로 하여, 최저이동거리가 나온 숫자만큼 1씩 더하게 바꾸었더니 다 성공함,

 

그러나 시간초과가 나타나서 효율성 테스트에서 걸림. 더 효율적인 제한사항을 고려해야함.

---

세 번째 시도

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

map<int, int> moveCount;

void Move(vector<int> nowpos, vector<vector<int>> Map, const vector<int>& target, int count = 0) {
    vector<vector<int>> NowMap = Map;
    NowMap[nowpos[0]][nowpos[1]] = 1;
    
    if (nowpos == target) {
        moveCount[count]++;
        return;
    }
    
    if(moveCount.size() > 0 && count >= moveCount.begin()->first)
        return;

    if (nowpos[0] + 1 < Map.size() &&
        Map[nowpos[0] + 1][nowpos[1]] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[0]++;
        Move(nextpos, NowMap, target, count+1);
    }

    if (nowpos[1] + 1 < Map[0].size() &&
        Map[nowpos[0]][nowpos[1] + 1] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[1]++;
        Move(nextpos, NowMap, target, count+1);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> Map(m);
    for (auto& def : Map)
        def = vector<int>(n);
    for (auto& def : puddles)
        Map[def[0] - 1][def[1] - 1] = 1;
    
    Move(vector<int>{0, 0}, Map, vector<int>{m - 1, n - 1});
    
    return moveCount.begin()->second % 1000000007;
}

실패

    if(moveCount.size() > 0 && count >= moveCount.begin()->first)
        return;

효율성 문제가, count가 넘어갔는데도 시도하는것 같아서 그럴경우 종료하게 만들었는데, 그래도 시간초과가 나타남.

더 다른 방법을 찾아봐야겠음.

---

네 번째 시도

#include <string>
#include <vector>
#include <map>

using namespace std;

map<int, int> moveCount;

void Move(vector<int> nowpos, const vector<vector<int>>& Map, const vector<int>& target, int count = 0) {
    
    if (nowpos == target) {
        moveCount[count]++;
        return;
    }

    if(moveCount.size() > 0 && count >= moveCount.begin()->first) {
        return;
    }

    if (nowpos[0] + 1 < Map.size() && 
        Map[nowpos[0] + 1][nowpos[1]] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[0]++;
        Move(nextpos, Map, target, count+1);
    }
    
    if (nowpos[1] + 1 < Map[0].size() && 
        Map[nowpos[0]][nowpos[1] + 1] != 1) {
        vector<int> nextpos = nowpos;
        nextpos[1]++;
        Move(nextpos, Map, target, count+1);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> Map(m);
    for (auto& def : Map)
        def = vector<int>(n);
    for (auto& def : puddles)
        Map[def[0] - 1][def[1] - 1] = 1;
    
    Move(vector<int>{0, 0}, Map, vector<int>{m - 1, n - 1});
    return moveCount.begin()->second % 1000000007;
}

실패

쓸모없어 보이는 생성문을 날렸다, 궂이 이동했던 Map을 갱신하지 않아도 된다는 사실을 꺠달았다.

그런데, 효율성 테스트만 실패했다. 뭔가 더 효율적인 방법을 찾아야 할듯.

---

다섯 번째 시도

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    vector<vector<int>> DP(n+1);
    for(auto& def : DP)
        def = vector<int>(m+1);
    for(auto& def : puddles)
        DP[def[1]][def[0]] = -1;
    
    DP[1][1] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(DP[i][j] == -1) continue;
            
            if(DP[i-1][j] != -1) DP[i][j] += DP[i-1][j];
            if(DP[i][j-1] != -1) DP[i][j] += DP[i][j-1];
        }
    
    return DP[n][m] % 1000000007;
}

실패

코드 전체를 손봐서, DP형태의 알고리즘인 A*형태로 길찾기 알고리즘을 정의하였다.

그런데도 효율성에서 실패가 나타남.

시간초과가 아니라 실패가 나타나는 이유를 찾아야함.

---

여섯 번째 시도

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    vector<vector<long>> DP(n+1);
    for(auto& def : DP)
        def = vector<long>(m+1);
    for(auto& def : puddles)
        DP[def[1]][def[0]] = -1;
    
    DP[1][1] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(DP[i][j] == -1) continue;
            
            if(DP[i-1][j] > 0) DP[i][j] += DP[i-1][j] % 1000000007;
            if(DP[i][j-1] > 0) DP[i][j] += DP[i][j-1] % 1000000007;
        }
    return DP[n][m] % 1000000007;
}

성공

아주 간단한 이유였는데, iostream으로 출력을 찍어보니까 값이 너무 넘쳐서 int형을 초과해버려 오버플로우 현상이 나타났던거였다....

long으로 해도 해결이 안되서 그냥 객체값 더하는 값에 1000000007나머지를 더하게 해도 값이 무방하게 나타나기 때문에 그렇게 하였더니 성공

 

이번 문제는 필요없는 생각을 하게만드는 코드인것 같다. 왜 이런식으로 만들었는지 알 수 없는 문제