프로그래머스 - 보행자천국(Level 3)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/1832

코딩테스트 연습 - 보행자 천국 | 프로그래머스

 

-문제-

 

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

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

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

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

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

 

m	n	city_map	answer
3	3	[[0, 0, 0], [0, 0, 0], [0, 0, 0]]	6
3	6	[[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]]	2

 

-접근-

 

1. city_map의 임의의 칸의 값이 2일 때 방향을 기억해야한다. (1)위에서 아래로 내려오는 경우, (2)왼쪽에서 오른쪽으로 가는 경우가 있기 때문에, (1)을 기억하기 위한 배열 city_v[501][501]선언, (2)를 기억하기 위한 배열 city_h[501][501]선언

2. 특정 인덱스에 있을 때, 위와 왼쪽만 확인하면 된다.

3. DP로 왼쪽과 위쪽을 누적해나가면서 최종 city_h[col-1][row-1]을 answer으로 출력한다.(city_v[col-1][row-1]을 answer으로 출력으로 무관하다. 왜냐하면 마지막 칸은 city_map=1이기 때문이다.)

 

 

-코드-

#include <vector>
#include <string.h>
#include <iostream>
using namespace std;

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

	memset(city_v, 0, sizeof(city_v));
	memset(city_h, 0, sizeof(city_h));

	int row = city_map.size();
	int col = city_map[0].size();

	city_h[0][0] = 1;
	city_v[0][0] = 1;

	// 첫번째 행 초기화 .
	for (int k = 1; k < col; k++) {
		if (city_map[0][k] == 0) {
			city_h[0][k] = city_h[0][k-1];
			city_v[0][k] = city_h[0][k - 1];
		}
		else if (city_map[0][k] == 1) {
			city_h[0][k] = 0;
			city_v[0][k] = 0;
		}
		else {
			city_h[0][k] = city_h[0][k - 1];
			city_v[0][k] = 0;
		}
	}

	//첫번째 열 초기화
	for (int k = 1; k < row; k++) {
		if (city_map[k][0] == 0) {
			city_h[k][0] = city_v[k-1][0];
			city_v[k][0] = city_v[k - 1][0];
		}
		else if (city_map[k][0] == 1) {
			city_h[k][0] = 0;
			city_v[k][0] = 0;
		}
		else {
			city_h[k][0] = 0;
			city_v[k][0] = city_v[k - 1][0];
		}
	}

	// 1행1열부터 위와 왼쪽만 확인하면서 DP
	for (int i = 1; i < row; i++) {
		for (int k = 1; k < col; k++) {
			if (city_map[i][k] == 0) {
				city_v[i][k] += (city_v[i - 1][k]+city_h[i][k-1]);
				city_h[i][k] += (city_v[i-1][k] + city_h[i][k-1]);

				city_v[i][k] %= 20170805;
				city_h[i][k] %= 20170805;
			}
			else if (city_map[i][k] == 1) {
				city_v[i][k] = 0;
				city_h[i][k] = 0;
			}
			else {
				city_v[i][k] += city_v[i - 1][k];
				city_h[i][k] += city_h[i][k-1];
			}
		}
	}

	answer = (city_h[row - 1][col - 1])% 20170805;
	return answer;
}