프로그래머스 등굣길 JAVA

코딩테스트 연습 - 등굣길

문제

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

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

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

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

조건

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

풀이

해당 문제는 dp로 문제를 해결하였다. 다만 문제 자체가 조금 이상하다. 일단 x, y 좌표가 반대로 주어주는데 반대로 주어진 걸 체크해서 문제를 해결하니 테케 1개만 맞추는 경우가 나왔고 반대인걸 그대로 사용하니 잘 해결되었다.

또 하나의 문제가 있었는데 모든 1행과 모든 1열은 다 1로 구성된다고 생각하여 모두 1로 박아놓고 시작했는데 만약 0,1 1,0 이 물웅덩이일 경우 결괏값이 0 이나와 야하지만 모두 1로 박아뒀기 때문에 0이 아닌 다른 값이 나와 오류가 발생하는 걸 알 수 있었다.

로직은 아래와 같이 구현하였다.

1. 물웅덩이는 -1로 표시해준다.

2. 0,0은 초기값 1로 지정한다

3. 2차원 배열을 탐색하면서 물웅덩이일 경우 0으로 초기화하고 빠져나온다.

4. 물웅덩이가 아니면 i, j값이 0인지 아닌지 판단해 0이 아닐 경우 왼쪽 값 혹은 위 값을 더해주고 나눠준다.

5. 최종 리턴을 해주는데 이때도 나눠준다.

코드

class Solution {
	 public static int solution(int m, int n, int[][] puddles) {
	        int[][] dp = new int[m][n];
	        for (int i = 0; i < puddles.length; i++) {
				dp[puddles[i][0]-1][puddles[i][1]-1] = -1; // 물웅덩이 표시
			}
	        dp[0][0] = 1; //초기값 지정
	        for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if(dp[i][j] == -1) { // 물웅덩이는 0으로 바꿔준다.
						dp[i][j] = 0;
						continue;
					}
					if(i != 0) 
						dp[i][j] += dp[i-1][j]%1000000007;
					if(j != 0) 
						dp[i][j] += dp[i][j-1]%1000000007;
				}
			}
	        return dp[m-1][n-1]%1000000007;
	 }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드