[프로그래머스]Lv.3 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

---

문제

• 계속되는 폭우로 일부 지역이 물에 잠겼습니다.
• 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다.
• 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예제

설계과정

1. 웅덩이는 경로의 수에 포함되면 안되므로 따로 처리한다.

 

2. 오른쪽으로 이동하는 경로와 아래쪽으로 이동하는 경로를 나누어서 가 좌표에 도달하는 경우의 수를 구한다.

 

3. 결과를 출력한다.

 

아래 블로그 글을 참조했다.

https://born2bedeveloper.tistory.com/34

[프로그래머스] 등굣길 - JAVA

---

풀이과정

1. 각 경로의 수를 저장할 2차원 배열 road[ ] 를 선언하고, n과 m에서 1씩 더해서 크기를 지정한다.

• 문제에서 시작 좌표가 (1, 1) 으로 시작한다고 적혀있기에 1씩 더해서 그에 맞게 크기를 설정한다.

2. 웅덩이에 해당하는 좌표에 도달했다면 해당 좌표의 값을 '-1' 로 설정해서 경우의 수에서 제외한다.

• road[ puddles[ i ][ 1 ] ] [ puddles[ i ][ 0 ] ] = -1;

3. 시작하는 곳은 무조건 1번의 경로가 생기는 것이기에 road[1][1] 에 1을 넣어준다.

 

4. 이중 for문을 통해 3가지 경우에 해당하는 경우의 수들을 계산한다.

 

5. 물웅덩이에 도달하면 무시하고 진행한다.

• 위쪽에서 구한 물웅덩이 값인 ' -1 ' 에 도달하면 continue; 를 통해 그대로 넘긴다.
• road[ i ][ j ] == -1

6. 위쪽에서 왔는데, 이미 도달한 경로가 존재하는 경우에는 이전까지 존재한 경로의 개수를 더해서 현재 좌표에 해당하는 경로의 개수를 만든다.

• 위쪽에서 왔다는 것은, 아래쪽으로 이동하고 있는 경우를 말한다.

7. 왼쪽에서 왔는데, 이미 도달한 경로가 존재하는 경우에도 마찬가지로 작업한다.

• 오른쪽으로 이동하는 경우를 말한다.

8. 결과를 출력한다.

---

답안소스

• 프로그래머스

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        int val = 1000000007;
		int[][] road = new int[n+1][m+1];
		
		for(int i=0; i<puddles.length; i++) {
			road[puddles[i][1]][puddles[i][0]] = -1;
		}
		
		road[1][1] = 1;
		for(int i=1; i<n + 1; i++) {
			for(int j=1; j<m + 1; j++) {
				if(road[i][j] == -1) continue;
				if(road[i -1][j] > 0) road[i][j] += road[i -1][j] % val;
				if(road[i][j -1] > 0) road[i][j] += road[i][j -1] % val;
			}
		}

        return road[n][m] % val;
    }
}

---

• 이클립스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int[][] puddles = new int[][] {{2,2}};
		
		int val = 1000000007;
		int[][] road = new int[n+1][m+1];
		
		for(int i=0; i<puddles.length; i++) {
			road[puddles[i][1]][puddles[i][0]] = -1;
		}
		
		road[1][1] = 1;
		for(int i=1; i<n + 1; i++) {
			for(int j=1; j<m + 1; j++) {
				if(road[i][j] == -1) continue;
				if(road[i -1][j] > 0) road[i][j] += road[i -1][j] % val;
				if(road[i][j -1] > 0) road[i][j] += road[i][j -1] % val;
			}
		}
		
		System.out.println(road[n][m] % val);
	}
}