Lv 3. 보행자 천국

 

https://school.programmers.co.kr/learn/courses/30/lessons/1832

프로그래머스

 

 

 

📌 자바(Java)로 푸는 보행자 천국 문제 풀이 🚦

---

🔎 문제 개요

이 문제는 프로그래머스 - 보행자 천국 문제입니다.
주어진 도시 지도(cityMap[][]) 에서 출발점(0,0)에서 도착점(m-1, n-1)까지 가는 경로의 개수를 구하는 문제입니다.
특정한 규칙(통행 불가 지역, 직진만 가능한 도로 등)이 존재하며,
경로의 개수를 MOD(20170805)로 나눈 나머지를 출력해야 합니다.

---

💡 예제 입력

int m = 3;
int n = 6;
int[][] cityMap = {
    {0, 2, 0, 0, 0, 0},
    {1, 0, 2, 2, 2, 0},
    {0, 0, 0, 0, 0, 0}
};

💡 예제 출력

2

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 동적 계획법(DP) 을 활용합니다.

✏️ 주요 고려 사항

✔ 두 가지 방향(오른쪽 →, 아래 ↓)으로만 이동 가능
✔ 통행 불가능한 도로(1)는 지나갈 수 없음
✔ 직진만 가능한 도로(2)는 현재 방향을 유지해야 함
✔ 도착점까지 갈 수 있는 모든 경로의 개수를 저장하여 해결

---

🔹 Java 코드 해설

import java.util.*;

class Solution {
    static final int MOD = 20170805; // 나머지 연산을 위한 상수

    public int solution(int m, int n, int[][] cityMap) {
        int[][] right = new int[m][n];  // 오른쪽으로 가는 경우의 수
        int[][] down = new int[m][n];   // 아래쪽으로 가는 경우의 수

        right[0][0] = 1;  // 시작점

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cityMap[i][j] == 1) continue;  // 통행 불가능한 경우

                // 왼쪽에서 오는 경우 (→ 방향)
                if (j > 0) {
                    if (cityMap[i][j - 1] == 2) right[i][j] = right[i][j - 1]; 
                    else right[i][j] = (right[i][j - 1] + down[i][j - 1]) % MOD;
                }

                // 위쪽에서 오는 경우 (↓ 방향)
                if (i > 0) {
                    if (cityMap[i - 1][j] == 2) down[i][j] = down[i - 1][j]; 
                    else down[i][j] = (right[i - 1][j] + down[i - 1][j]) % MOD;
                }
            }
        }

        return (right[m - 1][n - 1] + down[m - 1][n - 1]) % MOD;
    }
}

---

🔍 코드 설명

📌 1. DP 배열 정의

int[][] right = new int[m][n];  // 오른쪽으로 가는 경우의 수
int[][] down = new int[m][n];   // 아래쪽으로 가는 경우의 수

• right[i][j] : (i, j)에 도착했을 때 오른쪽(→) 방향으로 갈 수 있는 경로 개수
• down[i][j] : (i, j)에 도착했을 때 아래쪽(↓) 방향으로 갈 수 있는 경로 개수

---

📌 2. 시작점 초기화

right[0][0] = 1;

• 시작점(0,0)에서 출발할 수 있는 경로는 1개이므로 right[0][0] = 1 로 초기화

---

📌 3. 이중 반복문으로 DP 배열 채우기

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (cityMap[i][j] == 1) continue;  // 통행 불가능한 경우

• cityMap[i][j] == 1 인 경우(통행 불가능 지역)는 건너뛰기

---

📌 4. 왼쪽에서 오는 경우(→ 방향)

if (j > 0) {
    if (cityMap[i][j - 1] == 2) right[i][j] = right[i][j - 1]; 
    else right[i][j] = (right[i][j - 1] + down[i][j - 1]) % MOD;
}

• (i, j-1)에서 → 방향으로 오려면:
  1. cityMap[i][j-1] == 2 → 직진 도로라면 right[i][j] = right[i][j-1]
  2. 그렇지 않다면 (i, j-1)에서 오는 모든 경로 합산

---

📌 5. 위쪽에서 오는 경우(↓ 방향)

if (i > 0) {
    if (cityMap[i - 1][j] == 2) down[i][j] = down[i - 1][j]; 
    else down[i][j] = (right[i - 1][j] + down[i - 1][j]) % MOD;
}

• (i-1, j)에서 ↓ 방향으로 오려면:
  1. cityMap[i-1][j] == 2 → 직진 도로라면 down[i][j] = down[i-1][j]
  2. 그렇지 않다면 (i-1, j)에서 오는 모든 경로 합산

---

📌 6. 정답 반환

return (right[m - 1][n - 1] + down[m - 1][n - 1]) % MOD;

• 도착지(m-1, n-1)에서 오른쪽(right)과 아래쪽(down)의 모든 경로를 합산하여 반환

---

🔥 시간 복잡도 분석

연산	최악의 경우 수행 횟수	시간 복잡도
DP 배열 초기화	m × n	O(m × n)
DP 값 계산 (이중 반복문)	m × n	O(m × n)
총합		O(m × n)

✅ 완전 탐색(O(2^(m×n)))을 사용하면 시간 초과 → 동적 계획법(O(m×n))으로 최적화

---

🏆 정리

✅ 핵심 포인트

✔ DP를 활용하여 효율적으로 경로 개수를 구함
✔ 직진 도로(2)는 기존 경로를 유지해야 함
✔ O(m×n)의 시간 복잡도로 빠르게 해결 가능

---

🎯 이 알고리즘의 장점

✅ DP를 활용한 최적화된 풀이
✅ O(m×n)으로 빠르게 결과 계산 가능
✅ 대형 맵에서도 시간 초과 없이 해결 가능

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!