[프로그래머스/알고리즘] 등굣길

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

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다. 

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

입출력 예

m=4

n=3

puddles={{2,2}}

return=4;

문제 해결

0	0	0	0	0
0
0		-1
0

처음에 초기화할 때 첫 행 첫 열을 0으로 초기화 하고 1,1을 집으로 생각합니다

(1,0)과 (0,1)의 자리는 puddle이 있지 않는 이상 1로 정의 해주고

동적 계획으로 풀기 위해서 각 위치에 값은 자신의 왼쪽 값+자신의 위쪽 값이 집에서 해당 위치까지 갈 수 있는 최단 경로의 수가 됩니다.

그러나 해당 위치에 왼쪽 또는 위쪽에 puddle이 있을 수 있기 때문에 if로 제외해주면서 계산하시면 금방 풀립니다.

프로그래머스에서는 효용성이라고 시간제한 or 자료형 초과도 검사합니다.

제안사항에서는 격자의 크기가 100이하라 10000개면 int자료형안에 들어가지만 효용성에서는 저것보다 더 큰 것을 집어 넣는 것같습니다.

그래서 계산을 할 때 마다 1,000,000,007로 나눠줘야 효용성 문제도 해결되는 것 같습니다.

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
	int answer = 0;
	int i, j;
	vector<vector<long>> temp(n + 2, vector<long>(m + 2));
	for (int i = 0; i < puddles.size(); i++) {
		temp[puddles[i][1]][puddles[i][0]] = -1;
	}

	for (i = 1; i<n + 1; i++) {
		for (j = 1; j<m + 1; j++) {
			if (((i == 1 && j == 2) || (i == 2 && j == 1)) && temp[i][j] != -1) {
				temp[i][j] = 1;
				continue;
			}
			if (temp[i][j] == -1)
				temp[i][j] == 0;
			else if (temp[i][j - 1] == -1 && temp[i - 1][j] == -1)
				temp[i][j] = 0;
			else if (temp[i][j - 1] == -1)
				temp[i][j] = temp[i - 1][j];
			else if (temp[i - 1][j] == -1)
				temp[i][j] = temp[i][j - 1];
			else
				temp[i][j] = (temp[i - 1][j] + temp[i][j - 1]) % 1000000007;
		}
	}
	answer = temp[i - 1][j - 1];
	return answer;
}