프로그래머스. 등굣길

프로그래머스. 동굣길

등교길이 아니라 등굣길이라니

1. 문제

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

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

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

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

2. 제한사항

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

3. 풀이

• map[i][j]에서 목적지로 갈 수 있는 경로 수는 map[i-1][j] + map[i][j-1]이다. 이걸 처음부터 끝까지 웅덩이 없는 곳만 골라서 반복하면 된다.
• 집 -> 학교를 하니까 풀이가 생각이 안 나서 학교를 기준으로 보았다.
• 학교의 위와 왼쪽에서 올 수 있는 경우는 각각 한 가지씩이다.
• 학교의 학교에서 위로 한 칸 왼쪽으로 한 칸 이동한 위치는 오른쪽과 아래쪽으로 갈 수 있어서 두 가지이다.
• 여기까지 생각하고 학교에서 집으로 역추적 하기로 했다.
• 근데 loop를 반대로 돌리기 귀찮아서 지도를 뒤집기로 했다.
• 웅덩이도 맞춰서 뒤집어 주었다.
• 확실히 전 단계에서 확실히 처리된 값만 다루기 위해 row++를 먼저 해주고 col++를 해주었다.

➕ 추가(20년 9월 30일)

• 생각해보니까 세로 먼저 안 하고 가로 먼저 해도 된다.
• 난 돌멩이다. 돌멩

4. 처음 코드와 달라진 점

• 코드 차이는 별로 없는데
• 지도를 열심히 뒤집다가 생각해보니까 집에서 학교를 가나 학교에서 집을 가나 똑같다는 생각이 들었다. 난 멍청이다.
• x y만 조금 수정해주었다.
• 문제 구성 자체는 어렵지 않았는데 x와 y가 계속 발목을 잡았다.
• 그리고 2번 정도 수정해서 최종 제출 했는데
  1. 나머지 연산 안 해줌
  2. 웅덩이 연산 한군데 빼먹음
• 웅덩이 배열을 안 만들고도 할 수는 있을 것 같은데 bool 배열이고 있는게 훨씬 깔끔하게 나올 것 같아서 그냥 뒀다.
• 예외처리 많이 안하고 그냥 행과 열을 한 줄씩 추가해주면 코드가 더 깔끔해질 것 같았다. 수정했다.
• 행과 열을 하나씩 추가했더니 map[1][1]을 1로 초기화해도 loop 돌면서 0으로 다시 초기화시키길래 map[1][1]을 웅덩이로 처리해서 그냥 지나치게 해버렸다.

5. 코드(배열 크기 100X100)

#include <string>
#include <vector>

using namespace std;
int map[100][100];
bool puddle_map[100][100];
int solution(int m, int n, vector<vector<int>> puddles) {
    map[0][0] = 1;
    
    for(int i=0; i<puddles.size(); i++){
        int x = puddles[i][1] - 1;
        int y = puddles[i][0] - 1;
        puddle_map[x][y] = true;
    }
    
    for(int i=1; i<n; i++){
        if(puddle_map[i][0]) continue;
        map[i][0] = map[i-1][0];
    }
    
    for(int i= 1; i<m; i++){
        if(!puddle_map[0][i]) map[0][i] = map[0][i-1];
        for(int j=1; j<n; j++){
            if(puddle_map[j][i]) continue;
            map[j][i] = (map[j-1][i] + map[j][i-1]) % 1000000007;
        }
    }
    
    return map[n-1][m-1];
}

5-2. 코드(101X101)

#include <string>
#include <vector>

using namespace std;
int map[101][101];
bool puddle_map[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    
    for(int i=0; i<puddles.size(); i++){
        int x = puddles[i][1];
        int y = puddles[i][0];
        puddle_map[x][y] = true;
    }
    
    map[1][1] = 1;
    puddle_map[1][1] =true;
        
    for(int i= 1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(puddle_map[j][i]) continue;
            map[j][i] = (map[j-1][i] + map[j][i-1]) % 1000000007;
        }
    }
    
    return map[n][m];
}

➕ 21.09.01 추가

6. 풀이

• 크게 달라진 건 없고 puddle_map 배열을 만들지 않고 풀었다.
• puddle_map 배열을 만들지 않아 연산이 아주 조금 복잡해졌다.
• arr를 101 X 101 배열로 만든다.
  • i == 0 || j == 0인 배열의 항목은 0으로 초기화한다.
  • i == 0 || j == 0인 배열의 항목은 실제 길이 아니라 계산을 위해만 존재한다,
  • arr[1][1] = 1로 초기화 한다.
  • puddles의 위치의 arr는 0으로 초기화한다.
  • 0으로 초기화하면 다른 작업없이 더할 수 있다.
• arr[i][j] = arr[i-1][j] + arr[i][j-1]이다.
  • arr[1][1]이 다른 값으로 바뀌지 않기 위해 i == 1 && j == 1이면 건너뛴다.
  • puddle이 있는 위치는 계산을 하지 않고 건너 뛴다.
• arr[n][m]을 return하면 된다.

7. 코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int arr[101][101] = {0, };
    
    for (int i = 1; i < 101; ++i) {
        for (int j = 1; j < 101; ++j) {
            arr[i][j] = -1;
        }
    }
    for (vector<int> puddle : puddles) {
        arr[puddle[1]][puddle[0]] = 0;
    }
    
    arr[1][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (arr[i][j] == 0 || (i == 1 && j == 1)) continue;
            else arr[i][j] = (arr[i][j - 1] + arr[i-1][j]) % 1000000007;
        }
    }
    return arr[n][m];
}