🐹 등굣길

1. 문제 링크

등굣길

2. 코드

def solution(m, n, puddles):
    answer = 0
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    # dp 테이블 세팅
    # puddle 표시
    for y, x in puddles:
        dp[x][y] = -1
    # 세로 세팅
    for i in range(1, n+1):
        # 웅덩이 이후는 최단 거리 가는길 없음
        if dp[i][1] == -1:
            break
        dp[i][1] = 1
    # 가로 세팅
    for i in range(1, m+1):
        # 웅덩이 이후는 최단 거리 가는길 없음
        if dp[1][i] == -1:
            break
        dp[1][i] = 1
    
    # 최단 거리 개수 탐색
    for i in range(2, n+1):
        for j in range(2, m+1):
            # 현재 위치가 puddle인 경우 패스
            if dp[i][j] == -1:
                continue
            # 양쪽 모두 puddle 없는 경우
            if dp[i-1][j] != -1 and dp[i][j-1] != -1:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # 양쪽 모두 puddle인 경우
            elif dp[i-1][j] == -1 and dp[i][j-1] == -1:
                dp[i][j] = 0
            # 둘 중 하나만 puddle인 경우
            else:
                # 둘 중 puddle 아닌 개수 선택
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[n][m] % 1000000007

• 정확성

  테스트 1 〉	통과 (0.01ms, 10.2MB)
  테스트 2 〉	통과 (0.02ms, 10.3MB)
  테스트 3 〉	통과 (0.02ms, 10.1MB)
  테스트 4 〉	통과 (0.03ms, 10.2MB)
  테스트 5 〉	통과 (0.06ms, 10.5MB)
  테스트 6 〉	통과 (0.06ms, 10.1MB)
  테스트 7 〉	통과 (0.08ms, 10.3MB)
  테스트 8 〉	통과 (0.09ms, 10.2MB)
  테스트 9 〉	통과 (0.05ms, 10.4MB)
  테스트 10 〉	통과 (0.02ms, 10.3MB)

• 효율성

  테스트 1 〉	통과 (2.60ms, 10.3MB)
  테스트 2 〉	통과 (0.97ms, 10.4MB)
  테스트 3 〉	통과 (1.54ms, 10.2MB)
  테스트 4 〉	통과 (3.11ms, 10.3MB)
  테스트 5 〉	통과 (1.68ms, 10.2MB)
  테스트 6 〉	통과 (3.02ms, 10.2MB)
  테스트 7 〉	통과 (1.41ms, 10.2MB)
  테스트 8 〉	통과 (2.50ms, 10.3MB)
  테스트 9 〉	통과 (2.67ms, 10.2MB)
  테스트 10 〉	통과 (1.86ms, 10.2MB)

3. 해설

중학교 수학때 배웠던 경우의 수 최단 거리 개수 구하기를 사용했다.

위 그림에서 집과 학교를 꼭짓점으로 변경하여 다시 그리면

다음과 같이 최단거리의 개수가 10이 나온다.

이것은 현재 위치에서 각각 ‘위쪽 위치’와 ‘왼쪽 위치’까지의 최단 거리의 합을 이용한 것이다.

그렇다면 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 성립한다.

만약 물웅덩이를 마주치게 된다면 다음과 같은 경우가 있다.

1. 위, 왼쪽 모두 물웅덩이인 경우

   현재 위치는 갈 수 없는 위치로 간주하여 → dp[i][j] = 0

2. 위, 왼쪽 둘 중 하나가 물 웅덩이인 경우

   물 웅덩이의 최단거리는 0으로 간주하여 물 웅덩이가 없는 위치의 최단 거리 개수와 동일해진다.

   → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

   (이때, 물웅덩이 위치의 dp값을 이미 -1로 초기화 해두었으므로 max값으로는 물 웅덩이가 없는 위치의 dp값이 리턴된다)

따라서 위 경우를 만족시키도록 dp 배열을 초기화시키고 dp[n][m]을 리턴해준다.