[Programmers] 등굣길

프로그래머스 - 등굣길 문제 입니다.

 

문제

제한사항과 예

주의사항은 행, 열이 반대라는점과 시작 지점이 [0, 0]가 아닌 [1, 1] 입니다.

오른쪽과 아래로만 움직인다면 최단 경로는 어떻게 가더라도 동일합니다.

cost에 대한 것을 배제하고 경우의 수만 따지면 됩니다.

첫 번째 행과 열을 1로 만들어 주되, 물이 잠긴 곳의 뒷 부분 부터는 갈 수 없으므로 0으로 만듭니다.

그 후 [2, 2] 부터 경로의 갯수를 합산합니다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(vector<int> a, vector<int> b) {	// 내림차순 정렬
    if(a[0] != b[0]) return a[0] > b[0];
    else return a[1] > b[1];	// 행이 같으면 열로 정렬
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0, i, j;
    int ** map = new int*[m];	// 동적 할당
    
    for(i = 0; i < m; i++) {
        map[i] = new int[n];
    }
    
    sort(puddles.begin(), puddles.end(), cmp);	// 물에 잠긴 곳 좌표 정렬
    for(i = 0; i < m; i++) {    // 물에 잠긴 곳
        for(j = 0; j < n; j++) {
            if(puddles.size() != 0 && i == puddles.back()[0] - 1 && j == puddles.back()[1] - 1) {
                map[i][j] = 0;	// 잠긴 곳 0
                puddles.pop_back();
            }
            else {
                map[i][j] = -1;	// 잠기지 않은 곳 -1
            }
        }
    }
    
    map[0][0] = 1;	// 집
    for(i = 1; i < m; i++) {	// 첫 행을 1로
        if(map[i][0] == -1 && map[i - 1][0] == 0) {	// 앞이 물에 잠겼을 경우
            map[i][0] = 0;
        }
        else if(map[i][0] == -1) {
            map[i][0] = 1;
        }
    }
    
    for(i = 1; i < n; i++) {	// 첫 열을 1로
        if(map[0][i] == -1 && map[0][i - 1] == 0) {
            map[0][i] = 0;
        }
        else if(map[0][i] == -1) {
            map[0][i] = 1;
        }
    }
    
    for(i = 1; i < m; i++) {	// 경로 합산
        for(j = 1; j < n; j++) {
            if(map[i][j] == -1) {
                map[i][j] = (map[i - 1][j] + map[i][j - 1]) % 1000000007;
            }
        }
    }

    answer = map[m - 1][n - 1];
    return answer;
}