[프로그래머스] 등굣길

문제

[프로그래머스] 등굣길

실패 코드

from collections import deque

def bfs(school, puddles):
    queue = deque()
    queue.append((0, 0, 0)) # 행, 열, 거리
    
    drow = [0, 1] 
    dcol = [1, 0]
    candidate = []

    while queue:
        row, col, cnt = queue.popleft()
        
        if [row,col] == school:
            candidate.append(cnt)
            continue
            
        for i in range(2):
            x, y = row+drow[i], col+dcol[i]
            
            if [y+1, x+1] not in puddles and (x <= school[0] and y <= school[1]):
                queue.append((x, y, cnt + 1))
    
    return len(candidate)

def solution(m, n, puddles):
    school = [n-1, m-1]
    return bfs(school, puddles)

• 단순 bfs로 풀어서 정확성 테스트 tc 8번 시간초과, 효율성 테스트는 모두 시간 초과로 0점이 나왔다.
• 모든 경로를 탐색하며 최단거리를 찾는 BFS, DFS가 아니라 각 칸마다 거기까지 도달하는 최단 경로의 경우의 수를 저장해야하는 DP 문제였다.

정답 코드

def solution(m, n, puddles):
    m, n = n, m
    
    dp = [[0] * (n+1) for i in range(m+1)]
    puddle = [[0] * (n+1) for i in range(m+1)]
    
    # 웅덩이 위치를 1로 표기
    for x, y in puddles:
        puddle[y][x] = 1
        
    dp[1][1] = 1
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if [i,j] == [1,1]:
                continue
            if puddle[i][j] == 1:
                continue
                
            # [i][j]까지 갈 수 있는 경우의 수는,
            # 바로 위까지 갈 수 있는 경우의 수 + 바로 왼쪽까지 갈 수 있는 경우의 수
            dp[i][j] = dp[i-1][j] + dp[i][j-1] 
        
    return dp[m][n]%1000000007

정리

1. 어떤 경로의 경우의 수를 구하는 문제(모든 경로 탐색) 혹은 각 단계에서 최댓값을 갖는 경우
   ➡️ 이전 단계를 통해 다음 단계를 구함. 다이나믹 프로그래밍
2. 경로 중 최단 길이 혹은 경로를 구하는 문제
   ➡️ BFS, DFS