ALGORITHM/PROGRAMMERS
[프로그래머스] 등굣길
0298
2021. 8. 11. 11:11
https://programmers.co.kr/learn/courses/30/lessons/42898
코딩테스트 연습 - 등굣길
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =
programmers.co.kr
2021-08-11
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
static int[] dx = {-1, 0};
static int[] dy = {0, -1};
public int solution(int m, int n, int[][] puddles) {
int[][] arr = new int[n][m];
for(int i = 0; i < puddles.length; i++) {
arr[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
arr[0][0] = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++){
if((i == 0 && j == 0) || arr[i][j] == -1) continue;
for(int k = 0; k < dx.length; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == -1) continue;
arr[i][j] += (arr[nx][ny] % 1000000007);
}
}
}
return arr[n-1][m-1] % 1000000007;
}
}
|
cs |
#문제풀이
오른쪽과 아래로만 갈 수 잇어서, 왼쪽과 위만 체크하면서 진행했다.
맨 마지막에 정답 리턴하기 전에 % 해주지 않으면 효율성 터진다...
그리고 puddles 값 받을 때 n과 m 주의 해야한다
