JAVA 프로그래머스 Lv.3 등굣길
https://school.programmers.co.kr/learn/courses/30/lessons/42898
문제
- 입력으로 m ( 1 <= m <= 100 )과 n ( 1 <= n <= 100 )과 웅덩이의 위치 좌표가 들은 2차원 int 배열 puddles ( 0 <= puddles.length <= 10 ) 이 입력으로 들어옴.
- 학교가 있는 곳의 좌표는 (m, n)이며 둘 모두가 1인 경우는 주어지지 않는다.
- 집을 출발지로 오른쪽이나 아래쪽으로만 움직여서 학교에 도착하도록 할 때 최단 경로의 개수를 1000000007으로 나눈 나머지를 return.
초기 코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
boolean[][] ground = new boolean[n][m];
for (int i = 0; i < puddles.length; i++) {
ground[puddles[i][0] - 1][puddles[i][1] - 1] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i < n - 2 && j < m - 2 && ground[i][j + 2] && ground[i + 2][j]) {
ground[i][j] = true;
}
if(i < n - 1 && j < m - 1 &&!ground[i][j + 1] && !ground[i + 1][j]){
answer++;
}
}
}
answer %= 1000000007;
return answer;
}
}
어떻게 해야 될지 모르겠어서 일단 만들어본 코드이다.
어떤식으로 만든 코드냐면
해당 칸에서 오른쪽으로 두 칸에 있는 값과 아래쪽으로 두 칸에 있는 값 모두가 true일 때 갈 수 있는 길이 없다고 판단하여 해당 칸을 true로 바꾼다. (-> 이것부터 잘못된 것 같다. 해당 칸들이 true로 막혀 있더라도 돌아서 가면 아래나 갈 수 있는 길이 있는 것 같다.)
이후 해당 칸에서 오른쪽으로 한 칸에 있는 값과 아래쪽으로 한 칸에 있는 값 모두가 false일 때 갈 수 있는 길이 있다고 판단하여 answer의 값을 증가시켰다.
많이 틀린 것을 보아 아예 잘못 푼 것 같다.
문제를 다시 풀어야 될 것 같다.
수정한 코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int[][] ground = new int[n][m];
for (int i = 0; i < m; i++) {
ground[0][i] = 1;
}
for (int i = 0; i < n; i++) {
ground[i][0] = 1;
}
for (int i = 0; i < puddles.length; i++) {
ground[puddles[i][0] - 1][puddles[i][1] - 1] = -1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (ground[i][j] == -1) {
ground[i][j] = 0;
} else {
ground[i][j] = ground[i - 1][j] + ground[i][j - 1];
}
}
}
answer = ground[n - 1][m - 1] % 1000000007;
return answer;
}
}
누적합 방식으로 수정한 코드.
1행과 1열은 모두 1로 초기화하고, 웅덩이가 있는 곳은 -1로 바꾸어놓았다.
해당 좌표의 바로 위 값과 왼쪽 값을 더해 현재 좌표에 저장한다.
웅덩이(-1)를 만났을 때는 계산하지 않고, 이후 계산을 위해 해당 자리를 0으로 수정한다.
그런데 아무리 틀렸다고 하더라도 런타임 에러가 너무 많이 난다.
뭐가 문제지 보통 이런 배열이 나왔을 땐 인덱스의 배열 위치 이탈 인데 난 제대로 입력한 것 같은데 뭐가 문제일까.
수정한 코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int[][] ground = new int[n][m];
for (int i = 0; i < n; i++) {
ground[i][0] = 1;
}
for (int i = 0; i < m; i++) {
ground[0][i] = 1;
}
for (int i = 0; i < puddles.length; i++) {
ground[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (ground[i][j] == -1) {
ground[i][j] = 0;
} else {
ground[i][j] = (ground[i - 1][j] + ground[i][j - 1])% 1000000007;
}
}
}
answer = ground[n - 1][m - 1] % 1000000007;
return answer;
}
}
수가 너무 커서 그랬던 것 같다.
계산할 때 mod 계산을 같이 넣어주니까 괜찮아졌다.
실패는 좀 있지만 런타임 에러는 없다.
실패한 것들은 방금 계산해보니 어디가 틀린 줄 알겠다.
첫 행과 첫 열을 모두 1으로 초기화했는데 첫 행 또는 첫 열에 웅덩이가 있을 때 그 방향으로는 이후에 못 가게 되는 것을 고려하지 못했다.
최종 코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int[][] ground = new int[n][m];
for (int i = 0; i < puddles.length; i++) {
ground[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
int num = 1;
for (int i = 0; i < n; i++) {
if (ground[i][0] == -1) {
num = 0;
}
ground[i][0] = num;
}
num = 1;
for (int i = 0; i < m; i++) {
if (ground[0][i] == -1) {
num = 0;
}
ground[0][i] = num;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (ground[i][j] == -1) {
ground[i][j] = 0;
} else {
ground[i][j] = (ground[i - 1][j] + ground[i][j - 1]) % 1000000007;
}
}
}
answer = ground[n - 1][m - 1] % 1000000007;
return answer;
}
}
먼저 웅덩이의 위치를 배열에 -1으로 입력한다.
이후 1행과 1열을 초기화를 할 때 int 변수 num을 toggle 버튼처럼 이용하여 1행과 1열에서 웅덩이를 만나면 이후로는 0으로 초기화 하도록 했다. 아마 int 변수는 기본 값이 0이므로 웅덩이를 만났을 때 이후에 올 초기화를 하지 않아도 될 것 같다.
초기화 이후에는 배열 전체를 순회하며 웅덩이를 만났을 때는 계산을 하지 않고 웅덩이 해당 좌표를 0으로 초기화하고, 아닐 경우에는 해당 좌표의 바로 위에 있는 값과 바로 왼쪽에 있는 값을 더해 1000000007로 나머지 계산을 하여 해당 좌표에 저장할 수 있도록 하였다.