프로그래머스 연습 - 보행자 천국

문제 설명

보행자 천국

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

• 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
• 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
• 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

 

#include <vector>
#include <iostream>
 
using namespace std;
 
int MOD = 20170805;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    
    
    pair<int, int> MAP[501][501] = {make_pair(0,0),}; //first는 왼쪽에서 들어옴, second는 위에서 들어옴
    for(int i=0;i<m;i++)
    {
        if(city_map[i][0]==1)
            break;
        else
            MAP[i][0].second = 1;
    }
    
    for(int j=0;j<n;j++)
    {
        if(city_map[0][j] == 1)
            break;
        else
            MAP[0][j].first = 1;
    }
    
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(city_map[i-1][j]==2)
            {
                if(city_map[i][j-1] == 2)
                {
                    MAP[i][j].first = MAP[i][j-1].first;
                    MAP[i][j].second = MAP[i-1][j].second;
                }
                else if(city_map[i][j-1] == 1)
                {
                    MAP[i][j].first = 0;
                    MAP[i][j].second = MAP[i-1][j].second;
                }   
                else
                {
                    MAP[i][j].first = MAP[i][j-1].first + MAP[i][j-1].second;
                    MAP[i][j].second = MAP[i-1][j].second;
                }
            }
            else if(city_map[i-1][j] == 1)
            {
                if(city_map[i][j-1] == 2)
                {
                    MAP[i][j].first = MAP[i][j-1].first;
                    MAP[i][j].second = 0;
                }
                else if(city_map[i][j-1] == 1)
                {
                    MAP[i][j].first = 0;
                    MAP[i][j].second = 0;
                }   
                else
                {
                    MAP[i][j].first = MAP[i][j-1].first + MAP[i][j-1].second;
                    MAP[i][j].second = 0;
                }
            }
            else
            {
                if(city_map[i][j-1] == 2)
                {
                    MAP[i][j].first = MAP[i][j-1].first;
                    MAP[i][j].second = MAP[i-1][j].first + MAP[i-1][j].second;
                }
                else if(city_map[i][j-1] == 1)
                {
                    MAP[i][j].first = 0;
                    MAP[i][j].second = MAP[i-1][j].first + MAP[i-1][j].second;
                }   
                else
                {
                    MAP[i][j].first = MAP[i][j-1].first + MAP[i][j-1].second;
                    MAP[i][j].second =  MAP[i-1][j].first + MAP[i-1][j].second;
                }
            }
            MAP[i][j].first %= 20170805;
            MAP[i][j].second %= 20170805;
        }
    }
    int answer = MAP[m-1][n-1].first + MAP[m-1][n-1].second;
    answer %= 20170805;
    return answer;
}

 

음.. 다풀고 다른사람들거 한번 봤는데 되게 간단하게 풀었다 다들.. ㅋㅋ

나만 복잡하게 푼거 같다.

 

일단 나는 pair<int, int>[501][501] 행렬을 선언했다. 

각각 first는 왼쪽에서 들어온 경우의 수, second는 위쪽에서 들어온 경우의 수를 저장한다.

 

예전에 중학교 시절에 푼 최소 경로 문제 푸는 식을 이용해

1행의 모든 열과 1열의 모든 행을 1로 초기화 시켜준다.

초기화를 시킬때 1을 만나기 전까지 1로 해주고 1을 만나면 그냥 break 한다.

 

그리고 각 행렬이 (i-1,j), (i,j-1) 행렬의 값을 비교해서

어디로 들어왔는지를 정하고 각각 경우의 수를 생각해서 값을 넣어준다.

first를 왼쪽 second를 위쪽에서 들어왔다고 생각하면 내가 나눈 if문이 쉽게 이해 될것이다.

 

 

이 수들은 MOD보다 클수 있으므로 MOD로 나누어 준다.

마지막 답도 first와 second를 더하고 MOD로 나누어 주면 답이 출력된다.