[프로그래머스] 등굣길

링크

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

코딩테스트 연습 - 등굣길 | 프로그래머스

풀이

 

(1,1) 집에서 (m, n) 학교까지 최단거리의 개수를 구하는 문제있은데

물웅덩이를 피해서 지나가야 한다.

 

내가 만약 (3,3) 지점에 도달하기 위해서는 최단거리로 오기 때문에 나의 위쪽과 왼쪽에서 오는 것 2가지 밖에 없다.

이때 (3,3)로 오려면 (2,3)과 (3,2)에서 오는 것밖에 없다.

그렇다면 (3,3)에서의 경로의 수 = (2,3)에서 오는 경로수 + (3,2)에서 오는 경로수           라는 것을 알 수 있게 되고

 

dp 점화식을 세울 수 있게 된다

dp [i][j] = dp [i-1][j] + dp [i][j-1]

 

dp 식을 계산 하기 전에 맨 위쪽과 맨 왼쪽의 경로의 수는 항상 1이다.

그러나 맨 위쪽이나 맨 왼쪽에 물 웅덩이가 있을 때 그 뒤에 있는 경로는 갈 수 없기 때문에 0이 된다.

 

위의 초기화를 해준 후 물 웅덩이를 피해 (m, n)에 도달하면 최종 경로의 수를 찾아낼 수 있다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>

#define SIZE 110
#define MOD 1000000007
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

int board[SIZE][SIZE];
map<pair<int, int>, int> _map;
int solution(int m, int n, vector<vector<int>> puddles) {
	for (auto p : puddles) _map[{p[0], p[1]}] = 1;
	for (int i = 1; i <= m; i++) {
		if (_map[{i, 1}] == 1) break;
		board[i][1] = 1;
	}
	for (int j = 1; j <= n; j++) {
		if (_map[{1, j}] == 1)  break;
		board[1][j] = 1;
	}
	

	for (int i = 1; i < m; i++) {
		for (int j = 1; j <= n; j++) {
			board[i + 1][j] = (board[i][j] + board[i + 1][j - 1])%MOD;
			if (_map[{i +1, j}] == 1)board[i + 1][j] = 0;
		}
	}

	return board[m][n]%MOD;
}