[Java] 프로그래머스 등굣길

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=java# 

프로그래머스

목표 지점 까지 최단 경로의 총 개수를 구하는 문제

 

알아야 할 개념

• 경로 개수 세기
• 모듈로
• 삼항 연산자

풀이

문제를 잘 읽자 !!

 

처음에 최단 경로의 총 개수가 아니라 최단 거리를 구하는 줄 알고 삽질을 했다. 역시 문제를 정확히 이해하는 것이 중요한 것을 다시 한 번 깨달았다.

 

로직은 다음과 같다. 

1. 주어진 조건에 맞추어 웅덩이 위치, 0행, 0열을 초기화 한다. 
2. 개수 카운팅을 한다.
3. 정답을 리턴한다.

우선 웅덩이 위치랑 0행 0열을 모두 초기화 한다.

웅덩이가 있는 곳은 -1 로 먼저 초기화 하고, 0행 0열 탐색 하면서 1로 초기화 하다 웅덩이를 만난 순간 -1 로 초기화 한다. (도달 할 수 없으니 ) 

 

그 다음(1,1) 위치부터 개수 카운팅을 다음과 같은 원리로 한다. 현재 위치에 위쪽 + 왼쪽 개수를 할당한다. 

경로 개수 세기는 초등학교 수학때 한 번씩 해 봤을 것이다.

s 에서 e 로 가는 경로의 수 = 2

개수를 셀 때 다음과 같은 예외처리를 해준다. 

• 웅덩이를 만났을 때에는 개수를 세지 않아야 한다. 

웅덩이는 0 으로 처리 !

• 양쪽 다 웅덩이일 떄는 -1 로 할당한다. 

양쪽 다 웅덩이

• 경로가 1,000,000,007 을 넘어가면 모듈로 연산을 적용해야 한다. (모듈로는 나머지 라는 뜻)

큰 값은 나머지 연산으로 해결

 

주의

자바에서 향상된 for 문을 사용할 때 [[]] 같이 빈 배열도 실행 됨으로 주의할 것. ( index out of bound ) 에러 뜬다.

다음과 같이 if 문을 걸어주었다. 

if(puddles[0].length > 0){
            for(int x[] : puddles){
                map[x[1]-1][x[0]-1] = -1;
            }
        }

 

 

코드

자바

import java.util.*;
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int [][] map = new int[n][m];
        
        if(puddles[0].length > 0){
            for(int x[] : puddles){
                map[x[1]-1][x[0]-1] = -1;
            }
        }
        for(int i = 1 ;i < n; i++){
            map[i][0] = (map[i][0] == -1 | map[i-1][0] == -1) ? -1 : 1;
        }
        for(int j = 1 ;j < m ;j++){
            map[0][j] = (map[0][j] == -1 | map[0][j-1] == -1) ? -1 : 1;
        }
        for(int i =1;i < n; i++){
            for(int j= 1 ;j < m; j++){
                if(map[i][j] != -1){
                    int a = map[i-1][j] == -1 ? 0 : map[i-1][j];
                    int b = map[i][j-1] == -1 ? 0 : map[i][j-1];   
                    map[i][j] = (a+b) == 0 ? -1 : (a+b) % 1000000007;   
                }
            }
        }
        return map[n-1][m-1] == -1 ? 0 : map[n-1][m-1];
    }
}