[Lv3] 등굣길

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 이하인 자연수입니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교는 물에 잠기지 않았습니다.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

 

입출력 예 설명

 

---

 

고등학교 수학 확률과 통계에 나오는 경우의 수 문제입니다.

 

동적계획법(Dynamic Programming, DP) 문제는 역시 수학적으로 푸는 편이네요.

 

장애물을 생각하지 않았을 때, 길찾기의 경우의 수는 중복되는 것들을 포함한 경우와 같습니다.

 

여기서 가로4, 세로3이므로, (4+3)! / (4!*3!) 이 됩니다.

 

장애물이 생겼을 때는 장애물을 피하는 지점을 직접 설정해서 계산을 나누어 더합니다.

 

 

장애물의 위치는 문제마다 바뀔테고, 어떻게 최적의 지점들을 바뀌는 문제마다 설정할 것인가..로 생각했는데,

 

코드상으로는 이렇게 나누고 계산하는 것보다 그냥 가는게 빠르더군요..

 

물론 무작정 시작점(왼쪽위)에서 오른쪽/아래로 무한 DFS로 가면 시간초과/메모리초과에 걸립니다. DFS로 푸는게 아니라서..

 

 

지도와 같은 2차원 배열을 두고, 거기에 최단경로로 도달할 수 있는 경우의 수를 적습니다.

 

당연히 맨위 가로줄은 1111111...이 될 테고, 세로줄도 세로로 1111111...이 되겠죠.

 

이제 나머지 칸들은 찬찬히 오른쪽과 아래로 내려오면서 가로+세로를 한게 거기로 도달할 수 있는 경우의 수입니다.

 

 

우선, 문제가 가로m, 세로n으로 m*n으로 표현하네요.

 

보통 행렬은 행*열로 세로*가로인 n*m으로 표현하죠.

 

문제에서는 왼쪽위 집을 1,1이라고 하는데, 코드상으로는 0,0이라고 표현하고,

 

도착지를 m,n이라고 하는데, 코드상으로는 n-1,m-1이 되겠죠.

 

헷갈리지 않게 미리 정보를 설정합니다.

int[][] map = new int[n][m];
map[0][1] = 1;
map[1][0] = 1;
for(int[] arr:puddles) map[arr[1]-1][arr[0]-1] = -1;
for(int i=2;i<m;i++) {
    if(map[0][i]==0 && map[0][i-1]==1) map[0][i]=1;
    else break;
}
for(int i=2;i<n;i++) {
    if(map[i][0]==0 && map[i-1][0]==1) map[i][0]=1;
    else break;
}

위에서 설명한 부분을 압축했습니다. 우선 집에서 바로 오른쪽, 바로 아래는 웅덩이가 없으면 갈 수 있을테니 1로 표시.

 

웅덩이에 대한 위치(역순-1,역순-1 주의.)에는 구분상 음수를 적습니다. (위에서 1이었어도 웅덩이면 음수로 갱신)

 

그외 집에서의 가로줄과 세로줄을 웅덩이 다음부터 볼텐데, 웅덩이를 만나기 전이면 다 갈 수 있으니 1입니다.

 

웅덩이는 여전히 -1로 남을테고, -1 다음칸은 못 가니까 0으로 남습니다.

 

 

for(int i=1;i<n;i++) {
    for(int j=1;j<m;j++) {
        if(map[i][j]==0) {
            if(map[i-1][j]>0) map[i][j]=map[i-1][j]%1000000007;
            if(map[i][j-1]>0) map[i][j]=(map[i][j]+map[i][j-1])%1000000007;
        }
    }
}
return map[n-1][m-1];

행단위로 먼저 볼텐데, 웅덩이면 그대로 -1이고 계산 없습니다.

 

위가 웅덩이가 아니라면(-1이 아니고), 위에 도달할 수 있었다면(>0) 수를 가져옵니다.

왼쪽이 웅덩이가 아니고 위에 도달할 수 있었다면 수를 가져와서 더합니다.

순서는 상관없습니다.

 

이렇게 했을 때 행렬의 마지막값이 도착지에 도달 할 수 있는 경우의 수입니다.