[알고리즘문제] 프로그래머스 - 보행자 천국

600

m,n크기의 map이 주어질 때, 1,1에서 m,n까지 이동가능한 경로가 몇개 있는지 구하는 문제입니다. 단, 이동을 하는데는 다음과 같은 조건이 있습니다.

 

1. 오른쪽, 아래 방향으로만 움직일 수 있다.

2. 맵에서 0으로 표시된 부분은 오른쪽/아래 모두 이동 가능하다.

3. 맵에서 1으로 표시된 부분은 지나갈 수 없다.

4. 맵에서 2로 표시된 부분은 이전에 진행된 방향으로만 진행할 수 있다. 예를 들어, a->b로 이동하는데 x축으로 오른쪽으로 한 칸 이동했고 b는 2로 표시되어 있다면 b는 오른쪽으로만 이동할 수 있다)

 

1. bfs(시간초과)

처음에 dfs로 문제를 풀면 어떨까 생각을 했는데 map의 크기가 500 x 500이었기 때문에 시간이 너무 오래걸릴 것 같았습니다. 그래서 bfs로 문제를 풀었는데, 이 방법도 시간 초과가 걸리더라구요. 

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int MOD = 20170805;

struct pos{
    int dir; // 0은 일반인 경우, 1은 왼쪽에서 온 경우, 2는 위에서 온 경우
    int x;
    int y;
};


// 오른쪽, 아래
int dx[2] = {1,0};
int dy[2] = {0,1};

bool boundaryOverflow(int y,int x,int height, int width){
    if(y == height || x == width){
        return true;
    }
    return false;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int height, int width, vector<vector<int>> city_map) {

    int answer = 0;
    queue<pos> q;

    pos p;
    p.dir=0; 
    p.x=0;
    p.y=0;

    q.push(p);

    while(!q.empty()){
        pos p = q.front();
        q.pop();


        if(p.x == width-1 && p.y == height-1){ // 빼낸 pos의 위치가 도착지점이면 answer++;
            answer++;
        }else{
            if(city_map[p.y][p.x] == 0){
                for(int i=0;i<2;i++){
                    int newY = p.y + dy[i];
                    int newX = p.x + dx[i];

                    if(!boundaryOverflow(newY, newX, height, width) && city_map[newY][newX] != 1){     

                    pos newP;
                    if(city_map[newY][newX] == 0){  // 현재 위치가 0이고 새로운 위치가 0일 때
                        newP.dir=0;
                        newP.x=newX;
                        newP.y=newY;
                    }else if(city_map[newY][newX] == 2){ // 현재 위치가 0이고 새로운 위치가 2일 때

                        newP.x=newX;
                        newP.y=newY;

                        if((newX - p.x) == 1) newP.dir = 1;
                        if((newY - p.y) ==1) newP.dir=2;

                      }
                        q.push(newP);
                   }
                }
            }else if(city_map[p.y][p.x] == 2){ // 보행자 안전구역인 경우

                    int newY = p.y;
                    int newX = p.x;   

                    if(p.dir==1) newX++;
                    if(p.dir==2) newY++;


                    if(!boundaryOverflow(newY, newX, height, width) && city_map[newY][newX] != 1){   
                        pos newP;
                      if(city_map[newY][newX] == 0){ // 현재 위치가 2이고 새로운 위치가 0일 때
                         newP.dir=0;
                         newP.x=newX;
                         newP.y=newY;
                      }else if(city_map[newY][newX] == 2){ // 현재 위치가 2이고 새로운 위치가 2일 때
                         newP.x=newX;
                         newP.y=newY;
                         newP.dir=p.dir;
                      }
                        q.push(newP);
                }                
            }
        }
    }
    return answer % MOD;
}

 

 

2. dp

bfs 코드 삽질 하다가 결국 다른 사람들의 문제를 봤습니다. 몇몇 분들은 재귀, 탐색으로 풀었던데 음..제꺼 코드는 시간초과가 뜨더라구요. 아무튼 대부분 dp로 풀었고 저도 같은 방식으로 접근해 보았습니다.

 

먼저 다음과 같은 경우를 생각해 봅시다.

city_map[1][1] = city_map[1][0] + city_map[0][1] 입니다. 이 말은 즉, map[1][1]에 접근하는 방법은

 

city_map[0][0]-> city_map[0][1] -> city_map[1][1] : city_map[1][1] 위에서 접근하는 경우

city_map[0][0]-> city_map[1][0] -> city_map[1][1] : city_map[1][1] 왼쪽에서 접근하는 경우

 

총 두가지로 나누어서 생각할 수 있습니다. 그렇기 때문에 city_map[1][1] = city_map[1][0] + city_map[0][1] 이 성립합니다.

그렇다면 다음과 같이 생각해볼 수도 있겠네요.

 

city_map[1][1] = fromLeft[1][0] + fromTop[0][1] : 왼쪽에서 접근하는 경우와 위쪽에서 접근하는 경우로 나누었습니다.

 

그렇다면 위의 개념과 문제에서 제시한 조건을 잘 생각해보면 보행자 천국를 풀어봅시다.

 

조건 1 : 오른쪽, 아래로만 이동할 수 있습니다.

조건 2 : city_map[y][x]값이 0이면 오른쪽, 아래로 이동할 수 있습니다.

조건 3 : city_map[y][x]값이 1이면 이동할 수 없습니다.

조건 4 : city_map[y][x]값이 2이면 바로 앞에 진행했던 방향으로만 이동할 수 있습니다. 예를 들어 a->b이동하는데 x축을 기준으로 오른쪽              으로 한 칸 이동했다면 다음번에 무조건 오른쪽으로 이동해야만 합니다.

조건 5 : 결과값이 큰 경우를 대비해 % 20170805한 값을 return 한다.

 

fromLeft : city_map[y][x]값을 구할 때 city_map[y][x-1]값,  왼쪽에서 접근하는 경우

fromTop : city_map[y][x]값을 구할 때 city_map[y-1][x]값,  위쪽에서 접근하는 경우

 

1. city_map[y][x] == 0 인 경우

0인 경우는 왼쪽에서오는 경우, 위쪽에서 오는 경우를 모두 더하면 된다

 

2. city_map[y][x] == 1 인 경우

막혀서 갈 수 없기 때문에 city_map[y][x]=0으로 해주어여함, 그래야지 나중에 이 값을 참조할 때 +되지 않기 때문

 

2. city_map[y][x] == 2 인 경우

fromLeft[y][x]는 왼쪽에서 온 경우이기 때문에 왼쪽값을 그대로 넣어주면 됨 ->fromLeft[y][x-1]

fromTop[y][x]는 위쪽에서 온 경우이기 때문에 위쪽값을 그대로 넣어주면 됨 -> fromTop[y-1][x]

 

결국에는 우측최하단 값을 구하는 문제이기 때문에 fromLeft[m][n-1] + fromTop[m-1][n] % MOD값을 구하면 됩니다.

 

#include <vector>
#include <cstring>
#include <iostream>
 
using namespace std;
 
int MOD = 20170805;
 
int solution(int m, int n, vector<vector<int>> city_map) {
    
    int answer = 0;
    
    int fromLeft[501][501] = {0};
    int fromTop[501][501] = {0}; 

    fromTop[1][1] = fromLeft[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) {
                fromLeft[i][j] += (fromLeft[i][j-1] + fromTop[i-1][j]) %MOD;
                fromTop[i][j] +=  (fromLeft[i][j-1] + fromTop[i-1][j]) %MOD;
            }
            else if (city_map[i-1][j-1] == 1) {
                fromLeft[i][j] = 0;
                fromTop[i][j] = 0;
            } 
            else {
                fromLeft[i][j] = fromLeft[i][j-1];
                fromTop[i][j] = fromTop[i-1][j];
            }
        }
    }
    
    answer = (fromLeft[m][n-1] + fromTop[m-1][n]) %MOD;
    return answer;
}