Programmers. 등굣길

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 등굣길

문제 풀이

바로 풀릴 줄 알았는데 웅덩이가 각 경계선에 있는 경우 그 뒤로는 도달할 수 없음을 간과했다. 만약 시작점 바로 우측과 하단에 웅덩이가 있으면 최단 거리의 개수가 0이 될 수도 있음을 고려하자.

• 최단 거리를 기록할 2차원 배열을 생성한다.
• puddle의 원소마다 해당 자리에 INF를 넣어 갈 수 없음을 표기한다.
• 시작점으로부터 우측, 하단 경계선에 INF가 나오기 전까지 1로 바꾼다.
• [1][1]부터 시작하여 끝점까지 위와 좌측의 값을 더한다. 만약 위/좌측의 값이 INF이면 갈 수 없음을 의미하므로 0으로 간주한다.
• 도착점인 우측 하단의 값을 리턴한다.

python 코드

def solution(m, n, puddles):
    board = [[0] * m for _ in range(n)]
    INF = float('inf')
    for c, r in puddles:
        board[r - 1][c - 1] = INF
    for i in range(1, n):
        if board[i][0] == INF:
            break
        board[i][0] = 1
    for j in range(1, m):
        if board[0][j] == INF:
            break
        board[0][j] = 1
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == INF:
                continue
            a = board[i - 1][j]
            b = board[i][j - 1]
            if a == INF:
                a = 0
            if b == INF:
                b = 0
            board[i][j] = (a + b) % 1000000007
    return board[-1][-1]