[프로그래머스/C++] 보행자 천국 (2017 카카오코드 예선)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제풀이]

 

이 문제는 아래와 오른쪽으로만 차량이 이동할 수 있다.

그리고 통행이 전부 가능한 구간과 차량의 통행이 금지된 부분, 우회전 및 좌회전을 하지 못하는 구간 3개로 나눠져 있다. 

그러므로 내가 원래 아래방향으로 이동하고 있었는지, 오른쪽 방향으로 이동하고 있었는지를 알고 있으면 쉽게 풀 수 있다.

 

그래서 내가 원래 이동하는 방향이 아래방향인 경우의 수를 기록할 2차원 vector와 오른쪽 방향으로 이동하던 경우를 기록할 2차원 vector를 만들었다.

 

그리고 for문을 돌려 현재 위치가 모든 차량이 이동가능한 부분이라면, 내 위치에서 아래로 가는 차량과 오른쪽으로 가는 차량의 수를 합쳐 아래와 오른쪽으로 이동하는 차량에 추가했다.

ex) downCar[y+1][x] += downCar[y][x]+rightCar[y][x],  rightCar[y][x+1] += downCar[y][x]+rightCar[y][x]

 

만약 현재 위치가 회전이 안되는 구간이라면, 내 위치를 기준으로 아래쪽 길은 아래쪽으로 가는 차량의 수만 추가하고 오른쪽에는 오른으로 가는 차량만 추가했다.

ex) downCar[y+1][x] += downCar[y][x],  rightCar[y][x+1] += rightCar[y][x]

 

이렇게 위 과정을 처음 위치에서 1칸 이동해서 갈 수 있는 좌표 ~ n+m-2칸 이동해 갈 수 있는 좌표까지 탐색을 전부 하면 [m-1][n-1]에 차량의 경우의 수가 저장이 된다.

 

[아이디어 정리]

1. 아래로 이동하던 차량과 오른쪽으로 이동하던 차량을 구분한다.
2. 현재 좌표를 기준으로 차량이 이동할 수 있는지 판단하고 조건에 따라 경우의 수를 추가한다.
3. 오른쪽으로 이동해서 도착점에 도달하는 경우의 수와 아래로 이동해서 도착점에 도달하는 경우의 수를 더해 20170805로 나눈 뒤 return 한다.

 

 

Code

 

 

#include <vector>
using namespace std;

int MOD = 20170805;
int dy[2]={1,0};
int dx[2]={0,1};
int rm,rn;
vector<vector<int>> rightCar;
vector<vector<int>> downCar;
vector<vector<int>> realMap;

void CanGo(int y, int x)
{
    int ny,nx;
    for (int i=0; i<2; i++)
    {
        ny=y+dy[i];
        nx=x+dx[i];
        if (ny<rm&&nx<rn)
        {
            if (realMap[y][x]==0)
            {
                if (i==0){//아래로 내려갈 경우 둘다 추가
                    downCar[ny][nx]+=rightCar[y][x]+downCar[y][x];
                }
                else
                {
                    rightCar[ny][nx]+=rightCar[y][x]+downCar[y][x];
                }
            }
            else if(realMap[y][x]==2)
            {
                if (i==0){//아래로 내려갈 경우만 아래로 내려가는 차에 추가
                    downCar[ny][nx]+=downCar[y][x];
                }
                else
                {
                    rightCar[ny][nx]+=rightCar[y][x];
                }
            }
            downCar[ny][nx]%=MOD, rightCar[ny][nx]%=MOD;
        }
    }
}


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    rm=m, rn=n;
    realMap=city_map;
    rightCar=vector<vector<int>>(m,vector<int>(n,0));
    downCar=vector<vector<int>>(m,vector<int>(n,0));
    // 초기에 이동할 수 있는 방향
    if (city_map[1][0]!=1)
    {
        downCar[1][0]=1;
    }
    if (city_map[0][1]!=1)
    {
        rightCar[0][1]=1;
    }  
    for (int i=1; i<m+n-2; i++)
    {
        for (int x=0; x<n&&x<=i; x++)
        {
            int y=i-x;
            if (y>=0&&y<m)
            {
                CanGo(y, x);
            }
        }
    }
    return (rightCar[m-1][n-1]+downCar[m-1][n-1])%MOD;
}

 

---

 

재귀적으로 문제를 풀려고 했다가, 그냥 for문으로 반복해서 풀어도 풀릴 것 같아서 바로 풀었다.

대신 코드가 덜 깔끔해졌고 살짝 효율이 떨어진듯 하다;

 

프로그래머스