[Programmers] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

1. Python

def solution(m, n, puddles):
    if m == 1 or n == 1:
        return 0 if puddles else 1

    puddles = set([(y-1, x-1) for y, x in puddles])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for x in range(1, n):
        if (0, x) in puddles:
            continue
        dp[0][x] = dp[0][x-1]
    for y in range(1, m):
        if (y, 0) in puddles:
            continue
        dp[y][0] = dp[y-1][0]
    for y in range(1, m):
        for x in range(1, n):
            if (y, x) in puddles:
                continue
            dp[y][x] = dp[y-1][x] + dp[y][x-1]
    return dp[-1][-1] % 1000000007

 

2. C++

int solution(int m, int n, vector<vector<int>> puddles) {
    if (m == 1 or n == 1)
		return puddles.size() == 0 ? 1 : 0;
	
	set<pair<int, int>> puddlesSet;
	for (auto puddle : puddles) {
		puddlesSet.insert(make_pair(puddle[0]-1, puddle[1]-1));
	}
	int dp[m][n];
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			dp[i][j] = 0;
		}
	}
    dp[0][0] = 1;
	for (int x=1; x<n; x++) {
		if (puddlesSet.find(make_pair(0, x)) != puddlesSet.end()) continue;
		dp[0][x] = dp[0][x-1];
	}
	for (int y=1; y<m; y++) {
		if (puddlesSet.find(make_pair(y, 0)) != puddlesSet.end()) continue;
		dp[y][0] = dp[y-1][0];
	}
	for (int y=1; y<m; y++) {
		for (int x=1; x<n; x++) {
			if (puddlesSet.find(make_pair(y, x)) != puddlesSet.end()) continue;
			dp[y][x] = dp[y-1][x] % 1000000007 + dp[y][x-1] % 1000000007;
		}
	}
	return dp[m-1][n-1] % 1000000007;
}