[프로그래머스 Level 3] [동적계획법] 등굣길 (C++)

오랜만에 문제풀이로 돌아왔습니다.

이번 문제는 쉬워보여서 막 덤볐다가 간단한 문제에 막혀서 시간을 꽤 썼습니다.

중학교때쯤 풀었던 경로문제같은데, 망할 비때문에 경로가 막혀버리는 상황이 발생했습니다. 경로찾기보다는 이 경로가 막힌 경우를 어떻게 처리할 것인지가 핵심이 되는 문제였습니다. 저는 핵심을 경로찾기로 생각해서 아 쉽네~ 이러다가 된통 당했죠. 바로 해설로 넘어가겠습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =

programmers.co.kr

0. 문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

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

0.0. 제한사항

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

0.1. 입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

0.2. 입출력 예 설명

1. 풀이 과정

먼저 각 경로로 이동할 수 있는 최단거리의 수를 기록한 2차원 배열을 하나 만들어줍니다.

오른쪽과 아래로만 이동하는 경우 일반적인 최단 경로 탐색은 왼쪽 변과 윗 변에 모두 1로 채우고, 왼쪽과 위를 더한 것을 그 자리에 넣는 방식으로 처리할 수 있습니다. 하지만 일부 지역이 침수가 되버리면 이 방법에 문제가 생기죠.

[0][1]과 [1][0]지역이 침수가 되버리면 도착지점인 네모로 갈 수 있는 방법은 존재하지 않습니다. 만약 1로 채운 뒤에 침수 위치를 0으로 계산하게 되면 오류가 발생합니다.

그러므로, 이 방법으로는 문제를 풀 수 없습니다.

대처법으로는 시작 위치에만 1, 침수된 위치에 0을 넣고 index가 -1이거나(배열 밖의 범위를 참조하거나) 침수된 부분을 참조해야 하는 경우 왼쪽과 위를 더할 때 그 부분을 빼고 더해주면 됩니다. 저는 침수된 부분을 0으로 놓고 나머지 부분을 -1로 초기화해서 구분했는데, 구분 방법은 다양하기 때문에 편하신 대로 하시면 됩니다.

그리고 또 하나의 함정이 있는데, int형태로 만들게 되면 약 21억까지밖에 표현할 수 없습니다. 100x100의 경로는 이를 아득히 넘어갈 수 있기 때문에 매번 1000000007로 모듈러 처리를 해주셔야 정상적으로 2차원 배열에 값이 들어가게 됩니다. (안해주셔도 값은 들어가지만, 마지막에 answer에서 해 줘야 하는 모듈러 처리를 하기 전에 자릿수 초과 문제로 값이 왜곡됩니다. 결과적으로 자릿수만 초과하지 않으면 마지막에 해주셔도 상관 없습니다.) 정확성 테스트는 모듈러 처리 안해도 만점 나와요 ㅋㅋㅋ

2. 소스 코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int road[100][100];
    
    // 0. 전체를 -1로 초기화
    for(int i = 0; i < 100; ++i){
        for(int j = 0; j < 100; ++j)
            road[i][j] = -1;
    }
    
    // 1. 시작 지점을 1로 바꿈
    road[0][0] = 1;
    
    // 2. 물에 잠긴 지역 0으로 바꿈
    for(int i = 0; i < puddles.size(); ++i)
        road[puddles[i][0]-1][puddles[i][1]-1] = 0;
    
    // 3. 인덱스가 -1이면 더하지 않고, 물에 잠긴 지역은 변경X, 각 방법이 int범위를 초과할 수 있으므로 넣을 때마다 모듈러처리
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            if(road[i][j] == -1){
                if(i == 0 && j == 0)
                    continue;
                else if(i == 0)
                    road[i][j] = road[i][j-1] % 1000000007;
                else if(j == 0)
                    road[i][j] = road[i-1][j] % 1000000007;
                else
                    road[i][j] = (road[i][j-1] + road[i-1][j]) % 1000000007;
            }
        }
    }
    
    answer = road[m-1][n-1];
    return answer;
}