[프로그래머스 알고리즘 스터디] 4주차 - 등굣길

YUZAMIN
YUZAMIN
Hello, World! I'm YUZAMIN, a diligently endeavoring frontend developer 🐤💦
[프로그래머스 알고리즘 스터디] 4주차 - 등굣길

Summary

문제 설명 📑

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항 🚫

격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다. 물에 잠긴 지역은 0개 이상 10개 이하입니다. 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

문제 풀이 👩🏻‍💻

풀이

  • 각 칸에는 해당 칸에 도착할 수 있는 경우의 수가 적혀 있음

  • 숫자는 해당 칸과 이웃해있는 위, 왼쪽 칸에 적힌 숫자의 합과 같음

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 등굣길
def solution(m, n, puddles):
    # 경우의 수를 저장할 리스트 생성
    # m개의 칸이 n행 존재
    road_map = [[0 for _ in range(m)] for _ in range(n)]
    # (0, 0) 칸의 값은 1로 설정(초기값)
    road_map[0][0] = 1

    # m개의 칸이 n행 존재하므로
    for i in range(n):
        for j in range(m):
            # 만약 i와 j가 0이면 continue ((0, 0) 칸이므로)
            if i == 0 and j == 0:
                continue

            # 만약 (j + 1, i + 1) 칸이 물에 잠긴 경우
            # (puddles는 시작 좌표가(1, 1)일 때의 좌표이므로 i와 j에 1씩 더해줘야 함)
            if [j + 1, i + 1] in puddles:
                # (i, j) 칸의 수를 0으로 설정
                # 해당 좌표는 방문할 수 없으므로
                # 방문하는 경우의 수가 0임
                road_map[i][j] = 0

            # 물에 잠기지 않은 칸의 경우
            else:
                # 해당 칸에 방문할 수 있는 경우의 수는
                # (i - 1, j) 칸과 (i, j - 1) 칸에 방문할 수 있는
                # 각각의 경우의 수의 합
                road_map[i][j] = (road_map[i - 1][j] +
                                  road_map[i][j - 1]) % 1000000007

    # (0, 0)부터 (n - 1, m - 1) 칸까지 경우의 수를 구했으므로
    return road_map[n - 1][m - 1]

문제 출처