[프로그래머스] '등굣길' 알고리즘 풀이 - 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):
# 범위를 m+1, n+1로 잡아서 왼쪽, 위쪽으로 IndexError가 발생하는 것을 방지 + 웅덩이가 있을 경우 -1 
    maps = [[0 if [i,j] not in puddles else -1 for i in range(m+1)] for j 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 maps[i][j] == -1:  # 웅덩이가 있을 경우
                maps[i][j] = 0
            else:  # 웅덩이가 없을 경우 
                maps[i][j] = maps[i-1][j] + maps[i][j-1] # 왼쪽, 위쪽 값을 합한 값을 가짐
                
    return maps[-1][-1] % 1000000007

 

 

• Most2의 풀이

# 재귀로 풀이
def solution(m, n, puddles):
    info = dict([((2, 1), 1), ((1, 2), 1)])  # 초기값 설정 : ((x좌표, y좌표), 경로개수)

    for puddle in puddles:  # 웅덩이는 경로의 개수를 0으로 설정
        info[tuple(puddle)] = 0

    def func(m, n): # 재귀함수
        if m < 1 or n < 1: # m 혹은 n이 1보다 작다면
            return 0
        if (m, n) in info:  # info 안에 (m, n)이 있다면
            return info[(m, n)]  # info[(m, n)]의 값을 반환
        # setdefault : info에 첫번째 인자가 있다면 첫번째 인자를 반환, 없다면 두번째 인자를 반환
        return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
    return func(m, n) % 1000000007