프로그래머스 등굣길

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

프로그래머스

 

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m n puddles return

4

3

[[2, 2]]

4

---

 

알고리즘

1. 격자 생성 및 초기화

vector<vector<int>> map(m, vector<int>(n, 0));

코드를 사용할 때는 주의가 필요합니다.content_copy

먼저, m x n 크기의 2차원 벡터 map을 생성하고 모든 칸을 0으로 초기화합니다. 이 격자는 각 칸이 이동 가능한지 여부를 표시합니다.

 

 

2. 물 웅덩이 표시

for (const auto& puddle : puddles) {
  int puddleX = puddle[0] - 1;
  int puddleY = puddle[1] - 1;
  map[puddleX][puddleY] = -1;
}

코드를 사용할 때는 주의가 필요합니다.content_copy

입력받은 물 웅덩이 위치 정보를 기반으로 격자에서 해당 칸을 -1로 표시합니다. -1은 물 웅덩이를 의미하며 이동이 불가능합니다.

 

 

3. 최단 경로 탐색

 

3.1. DP 테이블 정의

vector<vector<int>> dp(m, vector<int>(n, 0));

코드를 사용할 때는 주의가 필요합니다.content_copy

m x n 크기의 2차원 벡터 dp를 생성합니다. dp[i][j]는 (i, j) 위치에 있는 칸까지 이동하는 가능한 모든 경로의 개수를 저장합니다.

 

3.2. 초기값 설정

dp[0][0] = 1;

코드를 사용할 때는 주의가 필요합니다.content_copy

집 위치 (0, 0)까지 이동하는 경로는 1가지 (오직 한 가지 방법으로만 이동 가능) 입니다.

 

3.3. 점화식 도출

(i, j) 위치에 있는 칸까지 이동하는 경로는 다음 두 가지 경우로 나눌 수 있습니다.

• 위쪽 칸에서 이동하는 경우: dp[i-1][j]
• 왼쪽 칸에서 이동하는 경우: dp[i][j-1]

따라서 다음과 같은 점화식을 도출할 수 있습니다.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

코드를 사용할 때는 주의가 필요합니다.content_copy

 

3.4. 반복문을 통한 탐색

for (int i = 1; i < m; ++i) {
  for (int j = 1; j < n; ++j) {
    if (map[i][j] == -1) continue;
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}

코드를 사용할 때는 주의가 필요합니다.content_copy

위에서 정의한 점화식을 기반으로 다음과 같은 방식으로 반복문을 수행하며 탐색합니다.

• (0, 0) 위치는 이미 초기화되어 있으므로 건너뛴다.
• 현재 칸이 물 웅덩이라면 건너뛴다.
• 위쪽 칸과 왼쪽 칸의 경로 개수를 더하여 현재 칸의 경로 개수를 계산한다.

 

 

4. 최종 결과

return dp[m-1][n-1];

코드를 사용할 때는 주의가 필요합니다.content_copy

탐색이 끝난 후 학교 위치 (m-1, n-1)에 저장된 값은 집에서 학교까지 이동하는 가능한 모든 경로의 개수를 의미합니다.

 

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> map(m, vector<int>(n, 0)); // 격자 생성 및 초기화
    const int MOD = 1000000007;

    // 집 위치는 1로 초기화
    map[0][0] = 1;

    // 물 웅덩이 위치는 -1로 표시
    for (const auto& puddle : puddles) {
        int puddleX = puddle[0] - 1; // 0-based index로 변환
        int puddleY = puddle[1] - 1; // 0-based index로 변환
        map[puddleX][puddleY] = -1;
    }

    // 집에서 학교까지의 최단경로 탐색
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (map[i][j] == -1) continue; // 물 웅덩이인 경우 pass
            if (i > 0 && map[i - 1][j] != -1) 
                map[i][j] += map[i - 1][j] % MOD; // 위쪽에서 오는 경우
            if (j > 0 && map[i][j - 1] != -1) 
                map[i][j] += map[i][j - 1] % MOD; // 왼쪽에서 오는 경우
        }
    }

    return map[m - 1][n - 1] % MOD; // 집에서 학교까지의 최단경로의 수 반환
}