【Algorithm】 [프머] 코딩테스트연습/ 동적계획/ 등굣길

07 Sep 2020 in Ubuntu / Language / Algorithm

등교길 문제 링크

동적 계획법 문제로 매우 쉬운 문제지만,

문제 잘못 읽어서, 오류 찾느라 시간을 많이 썼다…

puddles 가 당연히 [행][열] 의 index로 주어지는 줄 알았는데, 아니었다.

1. 정답 코드

def solution(m, n, puddles):
    # 동적 메모리 미리 만들기
    path_num = [[0 for i in range(m+1)] for j in range(n+1)]
    path_num[0][0] = 1

    # puddle 계산하기 쉽게
    for temp in puddles:
        temp[0] = temp[0] - 1
        temp[1] = temp[1] - 1

    # 맨 윗라인
    for j in range(1, m):
        if [j, 0] not in puddles:
            path_num[0][j] = path_num[0][j-1]

    for i in range(1, n):
        if [0, i] not in puddles:
            path_num[i][0] = path_num[i-1][0]

    # 나머지 아래 라인들
    for i in range(1, n):
        for k in range(1, m):
            if [k, i] in puddles:  # 순서 조심,  m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles
                path_num[i][k] = 0
            else:    
                path_num[i][k] = path_num[i-1][k] + path_num[i][k-1]

    return path_num[n-1][m-1] % 1000000007

2. 참고하면 좋은 코드

• 나의 코드와 흐름은 똑같다.

  def solution(m, n, puddles):
    # 문제에서는 1부터 시작하므로, 
    # 문제의 값과 일치할 수 있게 가로 m+1, 세로 n+1로 maps을 만들어준다.
    maps = [[0] * (m + 1) for _ in range(n+1)]
      
    # 시작점
    maps[1][1] = 1
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1:
                continue
            if [j,i] in puddles:
                maps[i][j] = 0
            else:
                maps[i][j] = (maps[i-1][j] + maps[i][j-1])
    return (maps[-1][-1]) % 1000000007