[C++로 풀이] 보행자 천국 (DP)⭐⭐⭐

📌 보행자 천국

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

🔥 1 차 풀이 : DP ⭕

자동차는 오른쪽, 아래쪽 이 2 가지 방향으로만 바라볼 수 있다. (자동차는 오른쪽, 아래 방향으로만 이동이 가능하다고 문제에서 주어졌기 때문이다.)

• 🟥 빨간색 글씨
  • 통행할 수 없는 곳이므로 오른쪽 바라볼 때 경로 수, 아래쪽 바라볼 때 경로수 모두 0 으로 설정
• ⬜ 하얀색 글씨
  • 첫 행은 통행 할 수 없는 곳 까지만 오른쪽 바라볼 때 경로 수를 1 로 지정한다.
  • 아래 쪽 바라볼 때 경로수는 0 으로 지정한다. (위쪽은 범위를 벗어난 지역이기 때문에 위에서 올 순 없기 때문이다.)
• 🟨 노란색 글씨
  • 예를 들어 (두 번째행, 네 번째 열)의 아래쪽 바라볼 때 방향의 경로수는 위쪽 지점이 자유롭게 통행할 수 있는 지점이였기 때문데 위쪽 지점의 아래쪽 바라볼 때 경로수, 오른쪽 바라볼 때 경로수를 모두 더해 결정하게 된다.
  • 이처럼 자유로운 지점으로부터 온 방향의 경로수는 노란색으로 표시함
• 🟧 주황색 글씨
  • 예를 들어 (세 번째행, 다섯 번째 열)의 오른쪽 바라볼 때 방향의 경로수는 왼쪽 지점이 회전할 수 없는 지점이였기 때문데 왼쪽 지점의 오른쪽 바라볼 때 경로수만 물려받아 결정하게 된다.
  • 이처럼 회전이 불가한 지점으로부터 온 방향의 경로 수는 방향이 일치하는 경로 수만 물려받기 때문에 이를 주황색으로 표시함

---

이처럼 지점이 2 인 경우! 즉, 좌회전 우회전이 금지되는 지점에선 2인 곳으로부터 수평 수직 방향이 일치하는 방향의 경로 수만 물려받아야하기 때문에 불가피하게 모든 지점이 2 가지 방향별로 경로 수를 저장하고 있어야 한다. 즉 바라보는 방향별로 경로 수를 저장해야 한다. 그러므로 dp 테이블을 (x좌표, y좌표, 방향) 이렇게 3차원 테이블로 설정하고 (x좌표, y좌표, 방향) 별로 경로수를 저장해야 한다. 나는 3 차원 배열을 사용하진 않았고 두 가지 방향별로 저장할 pair를 원소로 하는 2 차원 배열을 사용했다.

• 점화식
  • 첫 행 통행 불가한 곳이 등장할 때 까지만 👉dp[0][i].right = 1, 👉dp[0][i].down = 0
  • 첫 열 👉 통행 불가한 곳이 등장할 때 까지만 👉dp[0][i].right = 0, 👉dp[0][i].down = 1
  • 그 외
    • 👉 dp[i][j].right = 왼쪽에서 오는 경로 수
      • 왼쪽에서 오는 경로 수 dp[i][j].right
        • 왼쪽이 통행 불가한 지점이라면 : 0
          • 왼쪽에서 오는건 불가능
        • 왼쪽이 통행 자유로운 지점이라면 : dp[i][j - 1].down + dp[i][j - 1].right
          • 아래를 바라보는 방향으로 올 수도 있고(좌회전) 오른쪽을 바라보는 방향에서도 올 수 있다.(직진)
        • 왼쪽이 좌회전 우회전 불가능한 지점이라면 : dp[i][j - 1].right
          • 오른쪽을 바라보는 방향으로만 올 수도 있다.(직진) 좌회전이 불가하기 때문에 아래쪽을 바라보는 방향을 꺾을 수가 없기 때문이다.(수직 방향이였는데 수평 방향으로 바꾸려는 시도니까)
          • 따라서 왼쪽 지점에선 오른쪽을 바라보는 방향의 경로 수만 물려받을 수 있다.
    • 👉 dp[i][j].down = 위쪽에서 오는 경로 수
      • 위쪽에서 오는 경로 수 dp[i][j].down
        • 위쪽이 통행 불가한 지점이라면 : 0
          • 위쪽에서 오는건 불가능
        • 위쪽이 통행 자유로운 지점이라면 : dp[i - 1][j].down + dp[i - 1][j].right
          • 아래를 바라보는 방향으로 올 수도 있고(직진) 오른쪽을 바라보는 방향에서도 올 수 있다.(우회전)
        • 위쪽이 좌회전 우회전 불가능한 지점이라면 : dp[i - 1][j].down
          • 아래를 바라보는 방향으로만 올 수도 있다.(직진) 우회전이 불가하기 때문에 오른쪽을 바라보는 방향에선 꺾어서 내려올 수가 없기 때문이다.(수평 방향이였는데 수직 방향으로 바꾸려는 시도니까)
          • 따라서 위쪽 지점에선 아래를 바라보는 방향의 경로 수만 물려받을 수 있다.

해당 지점까지 올 수 있는 경로의 수 👉 dp[i][j].right + dp[i][j].down

두 방향까지의 경로의 수를 더하면 된다.

---

또한 덧셈 연산으로 인하여 경로 수가 계속해서 커지기 때문에 정수 표현 범위를 벗어날 것을 우려하여 20170805로 나눈 나머지를 리턴하라고 문제에서 지시하고 있다. 그러니, 덧셈 연산의 결과를 꼭 20170805로 나눈 나머지로서 테이블에 저장하도록 하자.

#include <vector>

using namespace std;

int MOD = 20170805;
#define down first
#define right second

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    
    // {아래쪽 바라볼 때 경로의 수, 오른쪽 바라볼 때 경로의 수} pair 를 원소로하는 2차원 dp 테이블
    // 일단 모두 {0, 0} 으로 초기화
    vector<vector<pair<int, int>>> dp(m, vector<pair<int, int>>(n, { 0, 0 })); 
    for (int i = 1; i < m; ++i){
        if (city_map[i][0] == 1) // 통행 불가한 지점이 나오지 않을 때 까지
            break;
        dp[i][0].down = 1; // 1 열의 아래쪽 바라볼 때 경로의 수는 1 로 통일
    }
        
    for (int i = 1; i < n; ++i){
        if (city_map[0][i] == 1) // 통행 불가한 지점이 나오지 않을 때 까지
            break;
        dp[0][i].right = 1; // 1 행의 오른쪽 바라볼 떄 경로의 수는 1 로 통일
    }
        
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            // down 아래쪽을 바라볼 때 (= 즉, 위쪽에서 왔을 때)
            if (city_map[i - 1][j] == 0) // 위쪽이 자유롭게 통행할 수 있는 지점이라면 -> 위쪽에서 직진도 가능, 위쪽에서 꺾어서 오는것도 가능
                dp[i][j].down = (dp[i - 1][j].down + dp[i - 1][j].right) % MOD; 
            if (city_map[i - 1][j] == 1) // 위쪽이 통행 불가한 지점이라면 -> 위쪽에서 오는건 불가능
                dp[i][j].down = 0; 
            if (city_map[i - 1][j] == 2) // 위쪽이 회전이 금지된 지점이라면 -> 위쪽에서 직진해서만 올 수 있음
                dp[i][j].down = dp[i - 1][j].down;

            // right 오른쪽을 바라볼 때 (= 즉, 왼쪽에서 왔을 때)
            if (city_map[i][j - 1] == 0) // 왼쪽이 자유롭게 통행할 수 있는 지점이라면 -> 왼쪽에서 직진도 가능, 왼쪽에서 꺾어서 오는것도 가능
                dp[i][j].right = (dp[i][j - 1].down + dp[i][j - 1].right) % MOD;
            if (city_map[i][j - 1] == 1) // 왼쪽이 통행 불가한 지점이라면 -> 왼쪽에서 오는건 불가능
                dp[i][j].right = 0;
            if (city_map[i][j - 1] == 2) // 왼쪽이 회전이 금지된 지점이라면 -> 왼쪽에서 직진해서만 올 수 있음
                dp[i][j].right = dp[i][j - 1].right;
        }
    }
    
    if (m == 1 && n == 1) // 도시가 1x1 크기라 출발지가 곧 도착지라면 답은 1 (경로가 가만히 있는 그 한 개 뿐)
        answer = 1;
    else
        answer = (dp[m - 1][n - 1].down + dp[m - 1][n - 1].right) % MOD; // 두 방향까지의 경로의 수를 더하면 그게 바로 그 지점까지 올 수 있는 모든 경로의 수
    
    return answer;
}

🔥 2 차 풀이 : DFS 시도 ⏰(시간초과)

#include <vector>

using namespace std;

int MOD = 20170805;
int M, N;
#define down 0
#define right 1

void DFS(vector<vector<int>>& city_map, int& answer, int r, int c, int dir) {
    if (r == M - 1 && c == N - 1) {  // 목적지에 도착할 때마다 경로수 +1
        answer = (answer + 1) % MOD;
        return;
    }

    if (city_map[r][c] == 0) { // 현재 지점이 자유롭게 통행할 수 있는 곳이라면 -> 2 가지 방향 모두 들어갈 수 있다.
        if (r + 1 < M && city_map[r + 1][c] != 1)
            DFS(city_map, answer, r + 1, c, down);
        if (c + 1 < N && city_map[r][c + 1] != 1)
            DFS(city_map, answer, r, c + 1, right);
    }
    
    if (city_map[r][c] == 2) { // 현재 지점이 회전이 불가능한 곳이라면 -> 현재 방향과 일치하는 곳으로만 들어간다.
        if (dir == down)
            if (r + 1 < M && city_map[r + 1][c] != 1)
                DFS(city_map, answer, r + 1, c, down);
        if (dir == right)
            if (c + 1 < N && city_map[r][c + 1] != 1)
                DFS(city_map, answer, r, c + 1, right);
    }
}

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    M = m;
    N = n;

    DFS(city_map, answer, 0, 0, down);

    return answer;
}

시간 초과나는 틀린 풀이입니다!

예제 2개는 다 맞는데 실행시키면 시간 초과나는 풀이이다. 예제들은 다 맞는 것 보면 이 DFS 자체가 틀린 풀이는 아닌듯 한데 아무래도 시간을 많이 잡아먹는듯 하다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기