등굣길 경로의 경우의 수

Haechan Kim·2021년 10월 14일
0

알고리즘

목록 보기
13/27
post-thumbnail

https://programmers.co.kr/learn/courses/30/lessons/42898
등굣길 경로의 경우의 수를 구하는 문제이다.
좌표 (1,1)인 집에서 부터 (m,n)인 학교까지 가는 경로를 구하는 문제인데 사이에 웅덩이를 피해 가야한다.
puddles[[2,2]]와 같이 2차원 배열로 웅덩이 좌표가 m, n과 같이 입력된다.
2차원 배열에서 최단 거리를 구하는 방법은 다음과 같다.

-> DP


public class Main
{
    public static int func(int m, int n, int[][] puddles)
    {
        int[][] street = new int [n][m]; // m을 열, n을 행
        street[0][0] = 1;
        for (int i=0; i<puddles.length; i++) // 웅덩이 있는 곳을 -1로 표시
            street[puddles[i][1]-1][puddles[i][0]-1] = -1;
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<m; j++)
            {
                if (street[i][j] == -1)
                { // 웅덩이 만날 경우
                    street[i][j] = 0;
                    continue; // 0으로 바꾸고 continue. 
                    // 0에서 더 더하면 안됨
                }
                if (i != 0) // 첫 행 아니면 위에 값 더함
                    street[i][j] += street[i-1][j];
                if (j != 0) //첫 열 아니면 왼쪽 값 더함
                    street[i][j] += street[i][j-1];
            }
        }
        
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<m; j++)
            {
                System.out.print(street[i][j] + " ");
            }
            System.out.println();
        }
        
        return street[n-1][m-1];
    }
    
    public static void main(String[] args) 
    {
    	int m = 6, n = 4; // 열과 행
        int[][] puddles = {{2,2}, {4,3}};
        func(m, n, puddles);
    }
}

0개의 댓글