알고리즘(C++) / 프로그래머스 level 3 : 등굣길

level 3 : 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898?language=cpp 

코딩테스트 연습 - 등굣길

 

코드

//프로그래머스 등굣길
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int visited[101][101] = { 0, };

    for (int i = 0; i < puddles.size(); i++) {
        visited[puddles[i][1]][puddles[i][0]] = -1;
    }

    visited[1][1] = 1; //집
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            //집
            if (i == 1 && j == 1)
                continue;
            //웅덩이
            if (visited[i][j] == -1)
                continue;

            //왼쪽 위쪽 모두 웅덩이 일때
            if (visited[i - 1][j] == -1 && visited[i][j - 1] == -1)
                visited[i][j] = 0; 
            //위쪽 웅덩이 일때 
            else if (visited[i - 1][j] == -1)
                visited[i][j] = visited[i][j - 1];
            //왼쪽 웅덩이 일때
            else if (visited[i][j - 1] == -1)
                visited[i][j] = visited[i - 1][j];
            else
                visited[i][j] = (visited[i - 1][j] + visited[i][j - 1])%1000000007;
       }
    }

    return visited[n][m];
}

int main() {
    int m = 4; int n = 3;
    vector<vector<int>> puddles = { {2,2} };
    cout << solution(m, n, puddles) << "\n";
    return 0;
}

 

설명

• visited 배열은 각 위치까지 갈 수 있는 최단경로의 개수를 저장한다.
• 집 위치는 1, 웅덩이의 위치는 -1로 한다. 
• 오른쪽과 아래쪽으로만 움직여 갈 수 있으므로 왼쪽과 위쪽을 합한 값이 최단경로의 개수이다. 
• 왼쪽이 웅덩이라면 위쪽의 값을, 위쪽이 웅덩이라면 왼쪽의 값을 가져온다.
• 학교가 있는 좌표까지 구한다면 최단경로의 개수를 구할 수 있다. 
• 값을 visited 배열에 저장하여 구하는 방식으로 DP(동적 계획법)으로 구할 수 있다.

 

고찰

걸린 시간 : 30분

DP 문제임에도 불구하고 풀이를 생각하는 것은 많이 어렵지 않았다. 하지만 정확성 테스트는 통과하였지만 효율성 테스트는 통과하지 못하였다.

정확성은 맞지만 효율성은 틀리는 이유 효율성 테스트 케이스가 넓이와 높이가 크게 설정되어 있는데 중간 계산 과정에서 int 사이즈를 넘어 overflow가 발생하기 때문에 중간에 계산할 때마다 %1000000007 해주어야 한다.