[프로그래머스] 보행자천국

문제

여행경로 (https://programmers.co.kr/learn/courses/30/lessons/1832)

풀이

1. 초기 접근

• 문제 조건 해석

  • city_map[i][j]의 상태(0, 1, 2) 에 따라 다음 경로를 처리해야함. -> dp? or dfs?

  • 주어지는 맵 크기 1 <= m, n <= 500 -> O(n^2) 으로 해결가능하다.

  • city_map[i][j] == 1 인 경우, 그 이전 방향 값을 알고있어야 다음 처리가 가능해진다.

• DFS

  • 초기에 dp로 시도해서 해봤지만 dp 배열안에, 방향 값을 넣기가 애매모호하고 복잡해서 생각나는대로 dfs로 구현했다.

  • 방향은 DOWN, RIGHT 로 미리 선언해두고 함수 파라미터로 이를 전달한다.

  • 현재 city_map[x][y] 의 상태에 따라, 다음 출발지를 정하여 탐색한다. x ==m-1 && y == n-1 일 경우, 탐색을 종료하고, 경로의 수를 올려준다.

• 코드

#include <vector>
#include <cstdio>
#define DOWN 1
#define RIGHT 2
​
using namespace std;
​
int MOD = 20170805;
​
int go(int x, int y, int m, int n, int d, vector<vector<int>>& city_map) {
    // range check.
    if (x == m-1 && y == n-1)
        return 1;
    if (x >= m || y >= n )
        return 0;
    
    if (city_map[x][y] == 0) {
        return go(x+1, y, m, n, DOWN, city_map) + go(x, y+1, m, n, RIGHT, city_map) % MOD;
    } else if (city_map[x][y] == 2) {
        if (d == DOWN)
            return go(x+1, y, m, n, DOWN, city_map) % MOD;
        else if (d == RIGHT)
            return go(x, y+1, m, n, RIGHT, city_map) % MOD;
    } else if (city_map[x][y] == 1) {
        return 0;
    }
}
​
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    for (int i=0 ; i<501 ; i++)
        for (int j=0 ; j<501 ; j++)
            memo[i][j] = 0;
    
    int answer = go(0, 0, m, n, DOWN, city_map);
    return answer;
}

2. 오류

• 시간 초과

  • 결과는 시간 초과였다. memoization을 사용하면 되지 않을까 했지만, 방향에 따라, 현재 [x][y] 의 가능한 경로의 수가 달라지기 때문에, memoization을 사용하지 못한다.

  • 1 <= m, n <= 500 이라 O(n^2) 으로 가능할 것으로 보였지만, 그래도 재귀호출 방식의 dfs 는 여전히 부담스러운 알고리즘이었나보다.

• 방향

  • 이 문제의 가장 핵심은, 직전 상태의 방향을 어떻게 알 것인가다. city_map[i][j] == 1 인 경우, 방향에 따라 어떻게 경로의 수를 넘겨줄 것인가.

3. 정답

• 카카오 해설 및 https://jaejin0me.github.io/post/algo44/ 분의 블로그를 참조했다.

• 방향에 따라 애초에 자료구조를 다르게 선언하여 dp로 풀었다. 왜 이 생각을 못했을까... 한 수 배워간다.

• 수정한 코드

#include <vector>
#include <string.h>
using namespace std;
​
int MOD = 20170805;
​
int V[501][501]; // i행 j열에서 아래쪽으로 갈 수 있는 경우의 수
int H[501][501]; // i행 j열에서 오른쪽으로 갈 수 있는 경우의 수
​
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer;
    memset(V, 0, sizeof(V));
    memset(H, 0, sizeof(H));
    
    V[1][1] = H[1][1] = 1;
    for (int i=1 ; i<=m ; i++) {
        for (int j=1 ; j<=n ; j++) {
            if (city_map[i-1][j-1] == 0) {
                V[i][j] += (V[i-1][j] + H[i][j-1]) % MOD;
                H[i][j] += (V[i-1][j] + H[i][j-1]) % MOD;
            } else if (city_map[i-1][j-1] == 1) {
                V[i][j] = 0;
                H[i][j] = 0;
            } else {
                V[i][j] = V[i-1][j];
                H[i][j] = H[i][j-1];
            }
        }
    }
    return V[m][n] % MOD;
}

4. 후기

2017 카카오코드 예선 문제였다. 정답률도 50%나 되는 비교적 쉬운 문제란다.

카카오 문제들을 보면, 뭔가 어디서 많이 본듯하고, 어떻게 하면 잘 풀 수 있을 것 같긴한데, 항상 제대로 풀리지가 않는다. 문제 역시 재밌게 구성되어있고, 진짜 실전에서 고민해볼만한 문제 내용들일거 같아서 재밌긴 한데... 항상 이런 식으로 어렵다.

2차원 배열을 아예 대놓고 이용하는 이런 문제들 보면, DFS, BFS, DP 중 하나인데, DP가 역시 시간초과에 가장 최적화 되어있다는 사실을 놓치면 안되겠다. 더불어, 위와같이 방향을 고려해야하는 경우, 애초에 두개의 자료구조로 나누어 따로 저장해나가는 방식 역시 숙지하고 있어야겠다.