보행자 천국_카카오_프로그래머스 lv3

https://programmers.co.kr/learn/courses/30/lessons/1832

프로그래머스

 

1. 풀이방법

 

이 문제에서 고려해야 할 조건은

 

1) 우측과 아래만 이동 가능하다.

2) citymap이 0일때는 자유롭게 이동가능, 1일때는 이동금지, 2일때는 직진만 가능.

3) %MOD를 계산시마다 해줄것.

 

1), 2)의 조건을 쉽게 풀기 위해서 dp배열을 왼쪽에서 오는 데이터 ( fromL ), 위쪽에서 오는 데이터 ( fromT ) 두개로 선언하고 각 조건들에 따라 맞춰서 계산해주면 된다

 

 

2. 코드 

 

#include <vector>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;

    //계산을 용이하게 하기위해서 시작점(1,1) 도착점 (m, n)으로 하겠음
    //city_map은 0,0 ~ m-1, n-1이므로 헷갈리지 말것
    int fromT[502][502];
    int fromL[502][502];
   
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            fromT[i][j] = fromL[i][j] = 0;

    //시작점 설정
    fromL[1][1] = fromT[1][1] = 1;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            //1. 자유로울때
            //자기자신을 더해주는건 더해주지 않으면 i=1, j=1일때 0+0이 덮어져서
            if (city_map[i - 1][j - 1] == 0)
            {
                fromL[i][j] = (fromL[i][j] + fromT[i - 1][j] + fromL[i][j - 1]) % MOD;
                fromT[i][j] = (fromL[i][j] + fromT[i - 1][j] + fromL[i][j - 1]) % MOD;
            }

            //2. 금지일때
            else if (city_map[i - 1][j - 1] == 1)
            {
                fromT[i][j] = fromL[i][j] = 0;
            }

            //3. 직진만 가능할때
            else
            {
                fromL[i][j] = fromL[i][j - 1];
                fromT[i][j] = fromT[i - 1][j];
            }
        }
    }


    return (fromL[m][n - 1] % MOD + fromT[m - 1][n] % MOD) % MOD;
}

 

 

 

 

3. 후기

 

이번에도 인터넷 형님들의 도움을 받아서 풀었다.

특히 헷갈렸던건 왜 자유로울때 fromT[i - 1][j], fromL[i][j - 1] 이거 두개를 더하는가 였는데 

 

(i-1, j-1)	(i-1. j)
(i, j-1)	(i, j)

 

(i, j)가 자유롭다면 (i-1, j), (i, j-1) 에서 오는 데이터를 받을수 있다.

(i, j) 에 입장에서 (i-1, j), (i, j-1) 는 각각 위에서, 왼쪽에서 오는 데이터이므로 당연한말이다.