[파이썬] 등굣길

문제 설명

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

 

입출력 예 설명

 

 

 

👩‍🦰 나의 풀이

def solution(m, n, puddles):
    dp=[[0]*(m+1) for _ in range(n+1)]
    dp[1][1]=1
    for i in range(1, n+1) :
        for j in range(1, m+1) :
            if i == j == 1 :    # 출발점
                continue
            if [j, i] in puddles :      # 물 웅덩이
                dp[i][j]=0
            else :
                dp[i][j]=(dp[i][j-1] + dp[i-1][j]) % 1000000007
    return dp[n][m]

0	0	0	0	0
0	1	1	1	1
0	1	0	1	2
0	1	1	2	4

물 웅덩이를 만나면 continue해도 됨. 초기값이 0이니까.

[i, j]가 아니라 [j, i]로 puddles에 담겨있음. [가로, 세로]

dp[i][j]는 왼쪽 경우의 수 dp[i][j-1], 오른쪽 경우의 수 dp[i-1][j]를 더한 경우의 수

 

 

# 실패
def solution(m, n, puddles):
    lst=list()
    def dp(x, y) :
        answer=0
        pos_x=[0, 1]
        pos_y=[1, 0] 
        
        for p in range(2) :
            if x == m-1 and y == n-1 :  # 도착
                return answer
            elif [dx, dy] in puddles :    # 물 웅덩이를 어떻게 표시하지    
                
            elif x < m and y < n :      # 범위 체크
                answer+=1
                dp(pos_x+x, pos_y+y)
        
    #dp=(0, 0)   # 집에서 출발
    dp(0, 0)
            
    return answer

 

오른쪽, 아래로 이동하게 만들려고 했다.

 

 

# 실패
def solution(m, n, puddles):
    #answer = 0
    visit=[[0]*m for _ in range(n)]
    
    def dfs(x, y) :
        global answer
        answer=0
        if visit[y][x] == 0 :   # 방문 한 적 없으면
            visit[y][x]=1       # 방문 처리
            if x == m-1 and y == n-1 :  # 학교 도착
                return answer
            elif [y, x] not in puddles :    # 웅덩이
                if x < m and y < n :  # 범위 체크
                    answer+=1
                    dfs(x+1, y)
                    dfs(x, y+1)
                
            
    a=dfs(0, 0)
    return a

 

IndexError: list index out of range 떴다.

오른쪽으로 쭉 가다가 길이 더 이상 없으면 아래로 간다.

dfs로 구현해 볼려고 했지만..ㅠ

 

 

👼 다른 사람 풀이

 

# https://codedrive.tistory.com/57
def solution(m, n, puddles) :
    answers=[[0]*(m+1) for i in range(n+1)]
    answers[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 :  # 물웅덩이
                answers[i][j]=0     
            else :
                # 위와 왼쪽 값 더하기
                answers[i][j]=answers[i-1][j]+answers[i][j-1]
    
    return answers[n][m] % 1000000007

 

 

문제의 조건처럼 1,1부터 시작하기 위해 [n+1][m+1] 크기로 answers를 생성했다.

현재 좌표는 위, 왼쪽 두 가지 방향에서 올 수 있다. 

풀이를 보면 쉬운데 이 아이디어가 잘 안 떠오르는게 문제😥

 

 

# https://copy-driven-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-ProgrammersPython-%EB%93%B1%EA%B5%A3%EA%B8%B8
def solution(m, n, puddles):
    answer = 0
    d=[[0]*(m+1) for _ in range(n+1)]
    
    d[1][0]=1   # 출발점
    
    for i in range(1, n+1) :
        for j in range(1, m+1) :
            if [j, i] in puddles :	# 물웅덩이
                d[i][j]=0
            else :
                d[i][j]=(d[i-1][j]+d[i][j-1])%1000000007
                
    return d[n][m]

 

위랑 알고리즘은 같지만 좀 더 간결한 코드

1,1 좌표 값을 굳이 처리할 필요없다. 위, 왼쪽 값 더해도 0이다.

 

 

 

 

문제 출처 💁‍♀️ 프로그래머스