프로그래머스 등굣길 (동적계획법, Dynamic Programming)

첨에 또 길찾기냐? 코드 재활용해야지 ㅋㅋㅋ 했는데 수학문제였다. 쿨럭...

문제 설명

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

입출력 예

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

입출력 예 설명

풀이

• 수학 문제인 줄 알았는데 웅덩이 위치가 어디인지 알 수가 없네?
  • 웅덩이가 학교를 막고 있으면 웅덩이 갯수가 적어도 학교로 갈 수가 없다.
    • 하지만 "집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다."라고 ㅋㅋㅋ
      • 그럼 수학 문젠가? 다시 ㅋㅋㅋ
• 그렇더라도 웅덩이 위치에 따라 갯수와 상관없이 답이 같을 수 있다.
  • 그럼 같게 만들면 되는거 아니냐???
    • 그럴 필요가 없다. 이동을 우측이랑 아래로만 갈 수 있으니 지도를 보정할 필요가 없다.

• 그리고 이 문제의 함정은
  • 좌표 문제
    • m x n을 m은 가로, n은 세로로 주고,
    • puddles의 좌표는 [[2,2]]로 줘놓고, 어떤게 가로, 세로인지 안 알려줬다는 점
    • 보통 상식적으로 m x n이 가로, 세로면, puddles도 가로 세로라고 생각하지...
    • 누가 뒤집어서 생각하겠냐고ㅋㅋㅋ (실수로 잘못 코딩하면 한번에 맞음)
  • 두번째는 최단경로...
    • 어차피 오른쪽이랑 아래로만 이동할 수 밖에 없기 때문에... 그냥 가면 최단경로임...
• 결론은 DP로 간다.
  • 오른쪽과 아래쪽으로 2명씩 닌자 분신술을 써서 분신이 몇 마리가 학교에 도착하는지를 답으로 쓰는 문제
    • 처음 집에서
      • 오른쪽 길이 비어있으면 오른쪽으로 분신 한명 보냄
      • 아랫쪽 길도 비어있으면 아랫쪽으로도 분신 한명 보냄
    • 분신은 이동하면서 본체와 마찬가지로 오른쪽으로 아랫쪽으로 분신을 만듬
    • 학교에 분신이 도착할 때 마다 +1
  • 나지막에 1000000007로 나누는 거 까먹지 않는다.
    • 구상은 끝. 이제 무지성 코딩 가즈아!
• 무지성으로 해서 그런가...???
  • 정확성 테스트는 다 통과인데, 효율성 테스트는 다 실패... 이상하다?

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.14ms, 10.4MB)
테스트 5 〉	통과 (0.17ms, 10.2MB)
테스트 6 〉	통과 (0.11ms, 10.3MB)
테스트 7 〉	통과 (0.21ms, 10.4MB)
테스트 8 〉	통과 (0.28ms, 10.6MB)
테스트 9 〉	통과 (0.11ms, 10.4MB)
테스트 10 〉	통과 (0.02ms, 10.2MB)
효율성  테스트
테스트 1 〉	실패 (23.34ms, 10.6MB)
테스트 2 〉	실패 (7.10ms, 10.4MB)
테스트 3 〉	실패 (9.52ms, 10.5MB)
테스트 4 〉	실패 (13.87ms, 10.4MB)
테스트 5 〉	실패 (12.20ms, 10.4MB)
테스트 6 〉	실패 (23.99ms, 10.5MB)
테스트 7 〉	실패 (8.48ms, 10.4MB)
테스트 8 〉	실패 (15.59ms, 10.4MB)
테스트 9 〉	실패 (17.96ms, 10.4MB)
테스트 10 〉	실패 (15.38ms, 10.4MB)

• 코드 아무리 봐도 뭐가 문제인지 모름... ㅋㅋㅋ
  • 게다가 주석을 다 지워버려서... 왜 저렇게 짯지? 헷갈림

def solution(m, n, puddles):
    닌자스 = []
    지도 = [[0 for _ in range(m)] for _ in range(n) ]
    
    닌자스.append([0,0])
    지도[0][0] = 1
    
    for puddle in puddles:
        x, y = puddle
        지도[y-1][x-1] = -1
        
    while len(닌자스) > 0:
        닌자수 = len(닌자스)
        for i in range(닌자수):
            x,y = 닌자스.pop(0)
            if x < m-1 and 지도[y][x+1] != -1:
                지도[y][x+1] += 지도[y][x]
                if [x+1,y] not in 닌자스:
                    닌자스.append([x+1,y])
            if y < n-1 and 지도[y+1][x] != -1:
                지도[y+1][x] += 지도[y][x]
                if [x,y+1] not in 닌자스:
                    닌자스.append([x,y+1])
                    
    return 지도[n-1][m-1] #학교에도착한분신갯수

• 병신 처럼 시간 낭비함. ㅋㅋㅋ
  • 리턴할 때 1000000007로 나눈 몫을 넘기라고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
    • 시간 낭비 오졌다.

def solution(m, n, puddles):
    닌자스 = []
    지도 = [[0 for _ in range(m)] for _ in range(n) ]
    
    닌자스.append([0,0])
    지도[0][0] = 1
    
    for puddle in puddles:
        x, y = puddle
        지도[y-1][x-1] = -1
        
    while len(닌자스) > 0:
        닌자수 = len(닌자스)
        for i in range(닌자수):
            x,y = 닌자스.pop(0)
            if x < m-1 and 지도[y][x+1] != -1:
                지도[y][x+1] += 지도[y][x]
                if [x+1,y] not in 닌자스:
                    닌자스.append([x+1,y])
            if y < n-1 and 지도[y+1][x] != -1:
                지도[y+1][x] += 지도[y][x]
                if [x,y+1] not in 닌자스:
                    닌자스.append([x,y+1])
                    
    return 지도[n-1][m-1] % 1000000007 #학교에도착한분신갯수

• 고수의 코드.... 효율성 개빠름
  • 아.. 위에 한줄 더 만들어서 인덱스 에러 방지. 대박이다.
    • 나도 처음에 닌자를 먼저 보내고 상/좌에서 값을 더하려고 했는데...
    • 몇번 짜다가 코드 에러 나서 포기했는데... 지금보니까 이렇게 하는게 더 쉽다.
    • 웅덩이 체크 안해도 되고, 그냥 값만 더하면 된다.

def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
    if puddles != [[]]:                    #물이 잠긴 지역이 0일 수 있음
        for a, b in puddles:
            grid[b][a] = -1                #미리 -1로 체크
    grid[1][1] = 1
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:                #(1,1)은 1로 만들어두고, 0이 되지 않도록
                continue
            if grid[j][k] == -1:           #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007   #[a,b] = [a-1,b] + [a,b-1] 공식

    return grid[n][m]
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 9.93MB)
테스트 4 〉	통과 (0.04ms, 9.96MB)
테스트 5 〉	통과 (0.05ms, 10MB)
테스트 6 〉	통과 (0.04ms, 9.99MB)
테스트 7 〉	통과 (0.06ms, 10MB)
테스트 8 〉	통과 (0.07ms, 10.1MB)
테스트 9 〉	통과 (0.04ms, 10.3MB)
테스트 10 〉	통과 (0.02ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (2.23ms, 10.3MB)
테스트 2 〉	통과 (1.17ms, 10.3MB)
테스트 3 〉	통과 (1.08ms, 10.2MB)
테스트 4 〉	통과 (1.99ms, 10.2MB)
테스트 5 〉	통과 (1.64ms, 10.4MB)
테스트 6 〉	통과 (2.41ms, 10.3MB)
테스트 7 〉	통과 (1.19ms, 10.3MB)
테스트 8 〉	통과 (1.72ms, 10.2MB)
테스트 9 〉	통과 (1.96ms, 10.4MB)
테스트 10 〉	통과 (1.92ms, 10.3MB)

• 그리고 이걸 딕셔너리로 하는 사람도 있네 ㅋㅋㅋ
  • 왜 딕셔너리로 하냐? 근데 내 코드 보다 빠름 ㅋㅋㅋㅋㅋㅋㅋㅋ

def solution(m, n, puddles):
    answer = 0
    info = dict([((2, 1), 1), ((1, 2), 1)])
    for puddle in puddles:
        info[tuple(puddle)] = 0

    def func(m, n):
        if m < 1 or n < 1:
            return 0
        if (m, n) in info:
            return info[(m, n)]
        return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
    return  func(m, n) % 1000000007
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.1MB)
테스트 4 〉	통과 (0.03ms, 10.1MB)
테스트 5 〉	통과 (0.10ms, 10.1MB)
테스트 6 〉	통과 (0.05ms, 10MB)
테스트 7 〉	통과 (0.06ms, 10.3MB)
테스트 8 〉	통과 (0.14ms, 10MB)
테스트 9 〉	통과 (0.11ms, 10MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (5.32ms, 11.1MB)
테스트 2 〉	통과 (2.23ms, 10.7MB)
테스트 3 〉	통과 (2.70ms, 10.6MB)
테스트 4 〉	통과 (3.95ms, 11.2MB)
테스트 5 〉	통과 (3.34ms, 10.6MB)
테스트 6 〉	통과 (5.40ms, 11.2MB)
테스트 7 〉	통과 (2.53ms, 10.5MB)
테스트 8 〉	통과 (4.03ms, 11.1MB)
테스트 9 〉	통과 (4.21ms, 11.1MB)
테스트 10 〉	통과 (4.21ms, 11.1MB)

• 암튼 이것도 삽질이니까 기록해두자
  • 경우의 수로 풀 수 있다고 착각했다가
  • 웅덩이 위치 때문에 그냥 길찾기로 하려고 했다가
  • 이전 결과를 더하면 되는 더하기라고 생각했는데
  • 구현하다가 코드에러나서 다시 닌자 보내기로 바꾼 결과물 ㅋㅋㅋ

• 다음 번엔 좀 더 생각해보고 이런 코드를 짜도록 해보자.
  • 완전 깔끔하네...

def solution(m, n, puddles):
    # dp table 생성 - padding
    dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
    # 출발지점 및 웅덩이 처리
    dp[1][1] = 1
    for puddle in puddles:
        dp[puddle[1]][puddle[0]] = -1

    # dp table 완성
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 만약 웅덩이라면
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
            dp[i][j] += dp[i-1][j] + dp[i][j-1]

    return dp[n][m] % 1000000007