[프로그래머스 LV 3 ] 등굣길 (파이썬/python)

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

########

이 문제 puddles 안에 있는 변수가

행, 열 순서가 아니라

열, 행 순서임 주의!!!

########

 

처음에 단순 bfs문제인줄 알았다.

하지만 엄청나게 많은 경우의수가 있을 수 있다는 점을 깨닿고

동적계획법을 이용해서 효율성을 높히는 방법에 대해 생각해보게되었다.

 

수능수학 확통시간에 목적지로 갈 수 있는 경로의 수 문제를 보면

이 문제를 기준으로

현재 위치를 기준으로 좌, 위 각각 갈 수 있는 값을 합하면

현재 위치로 갈 수 있는 경로의 수가 된다.

 

dp사용해서 푼 코드

def solution(m, n, puddles):
    # 매개변수가 반대로 있어서 너무 보기 까다로움, 바꿔주자
    m, n = n, m
    arr = [[0 for j in range(n + 1)] for i in range(m + 1)]
    dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
    # 웅덩이 표시
    for x, y in puddles:
        arr[y][x] = 1
    dp[1][1] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1 and j == 1:
                continue
            if arr[i][j] == 1:
                continue
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
 
    return dp[m][n] % 1000000007

 

 

 

bfs로 푼 코드(시간초과)와 결과

from collections import deque
 
answer = 0
 
 
def solution(m, n, puddles):
    arr = [[0 for j in range(m + 1)] for i in range(n + 1)]
    for x, y in puddles:
        arr[y][x] = 1
 
    def bfs():
        global answer
        nh = [1, 0]
        ny = [0, 1]
 
        q = deque()
        q.append([1, 1])
        while q:
 
            h, y = q.popleft()
            for i in range(2):
 
                dh = h + nh[i]
                dy = y + ny[i]
 
                if dh > n or dy > m:
                    continue
                if dh == n and dy == m:
                    answer += 1
                    continue
                elif arr[dh][dy] != 1:
                    q.append([dh, dy])
 
    bfs()
 
    return answer%1000000007