通学路(DP)
質問元:https://programmers.co.kr/learn/courses/30/lessons/42898
質問する
持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.
最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.
せいげんじょうけん論理ができたらエリアに挿入する. 移動方向は右下に固定されており、どこへ行っても最短経路が確保されている. dfsで解くとタイムアウトになる可能性があるのでDPで解きました. 主な論理は、各位置において自分の左上隅の値を表示し、この2つの値の和を自分の値とする.この値は、現在位置までの回数を意味します. この場合、2つの値のうちの1つも0と-1の場合の処理に注意する.いずれかの値が0の場合、2つの値のうちより大きな値で割り当てられます. 両値のいずれか1の場合、両数のうちより大きい値とし、両値とも負数であれば0とする. 配列の最後の要素値が正しい. 効率テストの最終実行%1億007は、まだ完全には理解できませんが、すべての値で実行する必要があります.
質問する
持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.
最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.
* 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
- m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
* 물에 잠긴 지역은 0개 이상 10개 이하입니다.
* 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int[][] map = new int[n + 1][m + 1]; // 1-base index
/**
* 시작 -> 1, 1(1행 1열)
* 끝 -> m, n(n행 m열)
*/
int[][] directions = {
{ -1, 0 }, // 윗쪽
{ 0, -1 }, // 왼쪽
};
if (puddles[0].length > 0) {
for (int i = 0, size = puddles.length; i < size; i++) {
int x = puddles[i][0];
int y = puddles[i][1];
map[y][x] = -1; // 웅덩이
}
}
map[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] != 0) continue;
int[] temp = new int[2]; // 0번 -> 위쪽, 1번 -> 왼쪽
for (int k = 0; k < 2; k++) {
int dy = i + directions[k][0];
int dx = j + directions[k][1];
// 탐색 가능한 범위인 경우
if (dy > 0 && dy <= n && dx > 0 && dx <= m) {
temp[k] = map[dy][dx];
}
}
if (temp[0] == 0 || temp[1] == 0) {
map[i][j] = Math.max(temp[0], temp[1]) % 1000000007;
} else if (temp[0] == -1 || temp[1] == -1) {
map[i][j] = Math.max(Math.max(temp[0], temp[1]), 0) % 1000000007;
} else map[i][j] = (temp[0] + temp[1]) % 1000000007;
}
}
answer = map[n][m] % 1000000007;
return answer;
}
}
Reference
この問題について(通学路(DP)), 我々は、より多くの情報をここで見つけました https://velog.io/@ghc1124/프로그래머스-등굣길DPテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol