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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1832

 

문제를 읽어보니 순간 두 가지 방법이 떠올랐다.-> dfs,bfs를 이용하는 방법, dp를 이용하는 방법.

이차원배열의 크기가 500*500=250000되는 것만 보아도 dfs,bfs를 이용하면 시간초과를 훌쩍 넘길 것을 예상할 수 있다.

게다가 20170805으로 나눈 나머지값을 리턴하라는 것만 보아도 시간초과를 예상할 수 있다.

당연히 방법은 dp를 사용하여야 한다.

 

<전체적인 알고리즘>

1.  배열은 이차원이라 d[502][502] 를 선언해야 하지만  각 위치마다  위에서 내려온 경로, 왼쪽에서 온 경로 두가지를 나눠 저장해야 했기때문에 d[502][502][2]를 선언하였다. 0은 위에서 온 경우,, 1은 왼쪽에서 온 경우로 정했다.

(city_map배열에서 도로가 2인경우는 그 방향대로 통과해야했기에 위에서 온 경로, 왼쪽에서 온 경로 따로 저장하였다.)

 

 2. 기본원리를 생각하면 해당 위치의 경로 개수는 위칸의 경로 개수 + 왼쪽칸의 경로 개수이다. 하지만 위칸이 2일경우에는 위칸의 위칸에서 내려온 경우만 통과하기 때문에 그 경우, 위칸에서 내려온 경로개수는 위칸의 위칸에서 내려온 경로 개수가 된다. 왼쪽에서 온 경로도 마찬가지로 생각하면 된다.

 

3. 결국 최종 개수는 m행 n열 칸의 위쪽에서 내려온 경로 수+왼쪽에서 온 경로 수 가 된다.

   (물론 20170805로 mod연산 해주는 것을 잊지 말자)

 

 

#include<iostream>
#include <vector>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    
    int d[502][502][2];  //3차 index가 0 -> 위쪽에서 온 경우 // 1 -> 왼쪽에서 온 경우   
    fill(&d[0][0][0],&d[499][499][2],0);
    
    d[0][0][0] = 1;  //이거 대신에 d[0][0][1]을 1로 세팅해도됨. 

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (city_map[i][j] == 1)continue;

			if (j > 0 && city_map[i][j - 1] == 2)   //위칸이 존재하며 2일 때
			{
				d[i][j][1] = d[i][j - 1][1];
			}
			else if(j>0)       // 위칸이 존재하며 위칸이 0일 때
			{
				d[i][j][1] = (d[i][j - 1][0] + d[i][j - 1][1]) % MOD;
			}

			if (i > 0 && city_map[i - 1][j] == 2)  //왼쪽 칸이 존재하며 2일 때
			{
				d[i][j][0] = d[i - 1][j][0];
			}
			else if(i>0)     //왼쪽 칸이 존재하며 0일때
			{
				d[i][j][0] = (d[i - 1][j][0] + d[i - 1][j][1]) % MOD;
			}
		}
	}

    int answer = (d[m - 1][n - 1][0] + d[m - 1][n - 1][1])%MOD; 
    return answer;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.