[프로그래머스][Python] 등굣길

문제를 정리해보자.

 

m x n 크기의 격자 모양이 있다. (1, 1)에는 집이 있고, (m, n)에는 학교가 있다.

일부 칸은 물에 잠겨 있다. 물에 잠긴 칸은 지나갈 수 없다.

집에서 학교까지 갈 수 있는 최단 경로의 개수를 구하자.

 

단, 이동은 오른쪽과 아래쪽만 가능하다.

 

 

풀이를 생각해보자.

 

이동은 무조건 오른쪽과 아래쪽으로만 가능하다. 따라서 어떻게 가도 최단 경로이다.

 

 

 

 

오른쪽 그림을 보자. 각 좌표까지의 최단 경로를 나타냈다.

마지막 (m-1, n-1)는 위에서 2가지, 왼쪽에서 2가지로 경로가 총 4가지이다.

 

((0, 0)이 시작이라고 잡았기 때문에 도착은 (m-1, n-1)이다.)

 

 

구현해보자.

 

BFS를 이용해서 (0, 0)부터 인접한 좌표로 이동하게 했다.

 

다만, check리스트를 이용해서 방문한 좌표는 다시 방문하지 않게 했다.

방문하지 않은 좌표의 값은 0, 방문한 좌표의 값은 1이다.

따라서 물 웅덩이는 BFS를 돌기 전에 미리 1로 바꿨다. (방문하지 않을 것이기 때문이다.)

 

 

 

 

이 문제는 범위도 신경써야 한다.

도착지점이 (m-1, n-1)에 있다. 따라서 i는 m-1, j는 n-1을 벗어나면 안된다.

(3, 0), (3, 1), (3, 2)는 아래쪽만 이동 가능하다.

(0, 2), (1, 2), (2, 2), (3, 2)는 오른쪽만 이동 가능하다.

 

방법은 2가지이다.

1. 조건을 만들어 범위를 벗어나지 않게 하기

2. 범위를 늘리기

 

2번을 선택했다. 그래서 (m, n)까지 가능하도록 했다. 

 

 

from collections import deque


def solution(m, n, puddles):

    check = [[0] * (n+1) for _ in range(m+1)]

    dp = [[0] * (n+1) for _ in range(m+1)]
    dp[0][0] = 1

    # 물 웅덩이
    for li in puddles:
        i, j = li[0]-1, li[1]-1
        check[i][j] = 1

    # BFS
    check[0][0] = 1
    queue = deque([[0, 0]])

    while queue:
        i, j = queue.popleft()

        if i <= m-1 and j <= n-1:
            dp[i+1][j] += dp[i][j]  # 오른쪽
            dp[i][j+1] += dp[i][j]  # 아래

            if check[i+1][j] == 0:  # 오른쪽 추가
                queue.append([i+1, j])
                check[i + 1][j] = 1

            if check[i][j+1] == 0:  # 아래 추가
                queue.append([i, j+1])
                check[i][j+1] = 1

    return dp[m-1][n-1] % 1000000007


solution(4, 3, [[2, 2]])

 

 

 

 

from collections import deque


def solution(m, n, puddles):
    dp = [[0] * (n+1) for _ in range(m+1)]
    dp[0][0] = 1

    # 물 웅덩이
    for li in puddles:
        i, j = li[0]-1, li[1]-1
        dp[i][j] = -1

    # 탐색
    for i in range(m):
        for j in range(n):
            if dp[i][j] != -1:
                if dp[i+1][j] != -1:
                    dp[i+1][j] += dp[i][j]  # 오른쪽

                if dp[i][j+1] != -1:
                    dp[i][j+1] += dp[i][j]  # 아래

    return dp[m-1][n-1] % 1000000007


solution(4, 3, [[2, 2]])

 

 

BFS를 대신 for문으로도 구현해봤다.

 

BFS와 다른 점은 좌표를 방문하는 순서이다. for문을 이용하면 (0, 0)부터 내림차순으로 (m, n)까지 방문한다.

 

이 때문에 for문으로 구현은 조건이 2개이다.

1. 현재 좌표는 물 웅덩이인가요?

2. 추가하려는 좌표는 물 웅덩이인가요?

 

BFS는 물 웅덩이가 아닌 곳만 다음 좌표로 가기 때문에 1번이 필요없었다.

 

그리고 물 웅덩이를 구분하기 위해 dp 값을 -1로 잡았다.

 

 

+ 제출 결과를 보니, 두 풀이법의 속도와 메모리 사용이 비슷하다.

 

 

 

 

처음에 오른쪽 사진에 있는 조건을 보지 못하고 제출을 했더니 효율성이 0점이 나왔다.

문제를 꼼꼼히 읽어야 겠다.