용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

[프로그래머스 Lv.3] 등굣길 (Python)
알고리즘/알고리즘 문제 풀이

[프로그래머스 Lv.3] 등굣길 (Python)

2024. 7. 27. 16:26

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

최단거리만 세면 되기에, 특정 칸에 진입할 수 있는 방법은 왼쪽 또는 위쪽으로 한정된다. 그렇기에 현재 칸에 도달할 수 있는 방법의 수는 현재의 왼쪽에 위치한 칸까지 도달할 수 있는 방법의 수와 현재의 위쪽에 위치한 칸까지 도달할 수 있는 방법의 수를 더한 값이다.

결론적으로 이전 값을 기반으로 하여 현재 값을 갱신해나가는 풀이가 진행되기에 DP로 이 문제를 풀이할 수 있다.

def solution(m, n, puddles):
    arr = [[0 for _ in range(m)] for _ in range(n)]

    def check(i, j): # 체크 대상 칸이 도달할 수 있는 칸인지 체크하는 함수
        is_i_valid = 0 <= i < n # 도달할 수 있는 열인지
        is_j_valid = 0 <= j < m # 도달할 수 있는 행인지
        is_not_puddle = arr[i][j] != -1 # 물에 잠긴 칸이 아닌지
        return is_i_valid and is_j_valid and is_not_puddle # 도달할 수 있는지 여부를 반환
        
    
    arr[0][0] = 1 # 시작하는 칸에 도달할 수 있는 방법은 한가지
    for x, y in puddles: arr[y-1][x-1] = -1 # 물에 잠긴 칸을 표시
        
    for i in range(n):
        for j in range(m):
            if arr[i][j] != 0: continue # 해당 칸의 값이 0이 아니라면 이미 체크한 곳임
            if check(i, j-1): arr[i][j] += arr[i][j-1] # 현재 위치의 왼쪽 칸이 도달할 수 있는 곳이라면 방법의 수를 업데이트
            if check(i-1, j): arr[i][j] += arr[i-1][j] # 현재 위치의 윗쪽 칸이 도달할 수 있는 곳이라면 방법의 수를 업데이트
    
    return arr[n-1][m-1] % 1000000007 # 최종 위치에 도달할 수 있는 벙법의 수 반환

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

[프로그래머스 Lv.2] 주식가격 (Python)  (5) 2024.09.21
[프로그래머스 Lv.4] 도둑질 (Python)  (0) 2024.08.30
[프로그래머스 Lv.3] 정수 삼각형 (Python)  (1) 2024.07.23
[프로그래머스 Lv.2] 후보키 (Python)  (0) 2024.07.21
[프로그래머스 Lv.3] N으로 표현 (Python)  (0) 2024.07.07
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • [프로그래머스 Lv.2] 주식가격 (Python)
    • [프로그래머스 Lv.4] 도둑질 (Python)
    • [프로그래머스 Lv.3] 정수 삼각형 (Python)
    • [프로그래머스 Lv.2] 후보키 (Python)
    용꿀
    용꿀

    티스토리툴바