[프로그래머스 Level3] 등굣길 - C언어(C++)

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 함수를 작성해주세요.

 

---

이런 최단거리+간선의 가중치가 모두 같은 길 찾기 문제는 바로 bfs로 진행해서 풀었던 적이 많은데 그렇게 하면 문제가 되는 점은 visited부분이다. 문제 예제를 예로 들자면 visited를 사용한다면 (3, 3) 위치를 지날 때 파란선과 노란선 중 미리 체크를 하고 하나의 선이 지나가면 다른 하나는 (3, 3)을 지나갈 수 없다ㅠㅠ

이에 대해 문제에서 제시된 동적 계획법(dp)를 사용했다.
문제에서 이동 시에는 무조건 오른쪽과 아래쪽으로만 움직일 수 있다고 말한 부분은 유의하자.

풀이 과정
0. 모든 영역으로 가는 최단 경로의 개수는 0으로 초기화한다.
1. 물에 잠긴 지역은 -1로 표시한다.
2. 처음 집의 위치에서 오른쪽과 아래쪽으로 각각 이동 가능한지 확인하고, 가능하다면 1로 표시.
3. 그 밖의 물웅덩이를 제외한 영역들은 각각 왼쪽과 위쪽에 최단 경로 개수를 더해주며 갱신한다.
- 단, 왼쪽과 위쪽 영역이 물 웅덩이가 아니어야 함
4. 마지막 학교 좌표의 최단경로 개수를 반환한다.

위 풀이대로 dp를 진행하면 문제 예제의 경우에는 다음의 행렬이 만들어진다.

0	1	1	1
1	-1	1	2
1	1	2	4

<< 전체 코드 >>

#include <string>
#include <vector>

using namespace std;

int map[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;    
    for (int i = 0; i < puddles.size(); i++) 
        map[puddles[i][1]][puddles[i][0]] = -1;
    
    if (map[1][2] == 0) map[1][2] = 1; // 집 위치에서 오른쪽으로 이동 가능
    if (map[2][1] == 0) map[2][1] = 1; // 집 위치에서 아래로 이동 가능
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == -1) continue;
            if (map[i][j-1] != -1) // 물 웅덩이가 아닌 왼쪽의 최단 경로 횟수 더함
                map[i][j] = (map[i][j] + map[i][j-1]) % 1000000007;
            if (map[i-1][j] != -1) // 물 웅덩이가 아닌 위쪽의 최단 경로 횟수 더함
                map[i][j] = (map[i][j] + map[i-1][j]) % 1000000007;
        }
    }
    return map[n][m];
}