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

Pixabay로부터 입수된 Pexels님의 이미지 입니다.

 

---

 

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

프로그래머스

 

 이번 문제는 도시의 도로 상태가 주어졌을 때, 문제의 조건에 따른 전체 경로 수를 구하는 문제이다. 자동차는 오른쪽, 밑으로만 움직일 수 있다. 그리고 도로의 상태는 0(제한 없음), 1(갈 수 없음), 2(이전 방향과 같은 방향으로만 이동 가능)로 구성된다. 이 문제를 처음 접했던 시기가 대략 1년 전이었던 것 같다. 처음에는 도착 지점부터 위, 왼쪽으로 역으로 진행하며 출발점에 도달할 수 있을 경우, 그 순간의 경로 수를 더해주는 방식으로 풀었었는데 틀렸었다. 그래서 더 고심하다가 결굴 다른 분의 풀이를 확인했었다. 그 때 보았던 풀이가 강렬했던 탓인지 내가 푼 방식이 그 방식과 너무 유사한 것 같다.

 각설하고, 이 문제는 다이나믹 프로그래밍 방식으로 풀 수 있다. 반복문을 진행하며 각 지점마다 갈 수 있는 방식을 찾아나가며 도착 지점까지 진행하면 된다. 이 때, 주의해야 할 점은 도로의 상태(city_map)의 값이다. 이 부분에 관해 내가 작성한 코드는 다음과 같다.

#define REC 1
#define DOWN 0
#define RIGHT 1

int record[MAX][MAX][2];

// ... 생략

if (city_map[r][c] == 0)
{
	record[r + REC][c + REC][DOWN] = (record[r + REC - 1][c + REC][DOWN] + record[r + REC][c + REC - 1][RIGHT]) % MOD;
	record[r + REC][c + REC][RIGHT] = (record[r + REC - 1][c + REC][DOWN] + record[r + REC][c + REC - 1][RIGHT]) % MOD;
}
else if (city_map[r][c] == 2)
{
	record[r + REC][c + REC][DOWN] = record[r + REC - 1][c + REC][DOWN];
	record[r + REC][c + REC][RIGHT] = record[r + REC][c + REC - 1][RIGHT];
}

 이 코드는 각 지점 (r, c)마다의 경로 수를 record[][][]에 저장하는 코드이다. 그런데 record의 좌표 r, c에 REC이라는 값을 더하고 있다. 이는 범위에 대한 우려 때문이다. 예를 들어 city_map[5][3]이 0일 때, (5, 3)인 곳에서의 경로를 구하기 위해서는 (4, 3)까지 경로 + (5, 2)까지의 경로일 것이다. 즉, (r, c)까지의 경로 수를 구하기 위해서는 r-1, c-1인 곳을 확인해야 하는데 record 탐색을 (0, 0)부터 시작한다면 (-1, 0)과 (0, -1)을 탐색하게 된다. 그리고 이는 에러를 일으키기에 record는 모든 좌표마다 (REC이라는 이름의)1만큼 보정을 해주었다.

 그리고 record는 3차원 배열이다. 첫 번째와 두 번째는 좌표의 r, c 값이 들어가며 마지막 2는 진행 방향을 의미한다. (아래는 DOWN, 0으로, 오른쪽은 RIGHT, 1로 매크로 상수를 이용해 지정하였다) 예를 들어, record[5][3][0]은 (5, 3)에서 아래로 갈 경우의 경로 개수이다. 이 때, city_map의 값이 0일 경우는 제한이 없기에 record[r][c][DOWN]과 record[r][c][RIGHT]의 값이 왼쪽 지점 경로 개수 + 위 지점 경로 개수로 같다. 하지만 city_map의 값이 2인 경우, 이전 방향과 같은 방향으로만 진행할 수 있으며, 이전 지점에서 현재 지점으로 직진하는 경우밖에 없기에 이전 지점 진행 방향의 경로 개수와 현재 지점 진행 방향의 경로 개수가 같은 값을 가진다. 그리고 city_map이 1인 경우는 어차피 못가기에 따로 처리하지 않았다. 아래는 이것들을 고려한 나의 코드이다.

 

#include <vector>
#define MAX 501
#define REC 1
#define DOWN 0
#define RIGHT 1
using namespace std;

int MOD = 20170805;
int record[MAX][MAX][2];

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int R = m;
    int C = n;
    
    for (int r = 0; r < MAX; ++r)
    {
        for (int c = 0; c < MAX; ++c)
        {
            record[r][c][DOWN] = 0;
            record[r][c][RIGHT] = 0;
        }
    }
    
    record[0 + REC][0 + REC][DOWN] = 1;
    record[0 + REC][0 + REC][RIGHT] = 1;
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            if (r == 0 && c == 0)
                continue;
            
            // city_map[r][c] == 1일 경우, 문제의 조건에 의해 가지 못한다.
            
            if (city_map[r][c] == 0)
            {
                record[r + REC][c + REC][DOWN] = (record[r + REC - 1][c + REC][DOWN] + record[r + REC][c + REC - 1][RIGHT]) % MOD;
                record[r + REC][c + REC][RIGHT] = (record[r + REC - 1][c + REC][DOWN] + record[r + REC][c + REC - 1][RIGHT]) % MOD;
            }
            else if (city_map[r][c] == 2)
            {
                record[r + REC][c + REC][DOWN] = record[r + REC - 1][c + REC][DOWN];
                record[r + REC][c + REC][RIGHT] = record[r + REC][c + REC - 1][RIGHT];
            }
        }
    }
    
    return record[R][C][DOWN];
}

 마지막 return은 record[R][C][DOWN]을 반환한다. 왜냐하면 문제의 조건에 '도착점의 city_map[i][j] 값은 0이다.' 라고 되어 있고 city_map의 값이 0일 경우에는 record[][][DOWN]과 record[][][RIGHT]의 값이 같기에 둘 중 어느 것을 반환해도 된다.

 

 

---

 참고한 글

https://yabmoons.tistory.com/538

[ 프로그래머스 보행자 천국 (Lv3) ] (C++)