[프로그래머스] '등굣길' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

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

 

 

알고리즘 분석

 

• 풀이

# for 문 풀이
def solution(m, n, puddles):
    dynamic = [[0] * (m+1) for _ in range(n+1)]  #왼쪽, 위로 한줄씩 만들어서 IndexError 방지

    dynamic[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:  # 웅덩이가 존재할 경우
                dynamic[i][j] = 0
            else:  # 웅덩이가 없을 경우
                dynamic[i][j] = dynamic[i-1][j] + dynamic[i][j-1]
    return dynamic[-1][-1] % 1000000007

 

 

• Most 풀이

# 재귀로 풀이
def solution1(m, n, puddles):
    answer = 0
    info = dict([((2, 1), 1), ((1, 2), 1)]) # 초기 시작 값
    for puddle in puddles: # 물 웅덩이들의 좌표를 차례로 가져옴
        info[tuple(puddle)] = 0 # 물 웅덩이의 좌표를 키 값에 대해 0이란 값을 지정 

    def func(m, n): # 최단경로를 구하는 재귀 함수 
        if m < 1 or n < 1: # m이나 n이 1보다 작을 경우 
            return 0 # 0을 반환 
        if (m, n) in info: # 키 값이 (m, n)인 값이 info에 존재할 경우 
            return info[(m, n)] # 키 값에 대비되는 값을 반환. 즉, 웅덩이일 경우 0 반환
        # setdefault를 이용
        # (m, n)이 존재하면 (m, n)을 반환하고 아닐 경우는 2번째 인자를 반환
        # 2번째 인자가 반환되면 재귀함수의 역할을 하게 된다.
        return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
    return func(m, n) % 1000000007

 

두 개의 풀이는 런타임이 거의 비슷하다.

하나는 for문, 하나는 재귀로 풀었다는 것이 차이점 

 

하지만 재귀함수에 배울 것이 많다고 생각한다. 

특히, 딕셔너리로 문제를 풀었다는게 굉장히 새로웠다. 항상 리스트나 튜플을 이용할 생각만 했는데, 딕셔너리와 재귀의 활용법을 제대로 보여준 풀이였다고 생각한다.