[1일 1알고] 보행자 천국

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

프로그래머스

---

특정 조건을 지키며 이동가능한 모든 경우의 수를 계산하는 문제입니다.

 

1인 경우 일반적인  장애물입니다.

2일 때가 중요한데 2는 회전을 할 수 없도록 하는 표지판입니다.

따라서 r, c위치정보 + 방향에 대한 정보가 필요한 것을 알 수 있습니다.

 

또한 문제에서 MOD를 하라고 하는 것으로 보아 경우의 수가 매우 커질 수 있음도 알 수 있습니다.

---

저는 그래서 일단 city_map과 별개로 이동하는 가짓수를 체크하는 dist_map을 별도로 만들었습니다. 이는 3차원으로 마지막 차원은 방향을 의미합니다.

 

다행히도 오른쪽과 아래로만 이동하기 때문에 더 깊이 따질 것은 없습니다.

---

#include <vector>
#include <queue>

using namespace std;

int MOD = 20170805;

enum Dir
{
    START = -1,
    RIGHT = 0,
    DOWN = 1
};

struct Move
{
    int r, c;
    Dir dir;
};

// 1 1 1 1 1 1
// 1 1 2 3 0 0
// 0 1 3 12 24 48

// MxN크기의 격자
// 자동차는 우 혹은 하 방향으로 한 칸씩 이동
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;

    if (m == 1 && n == 1)
        return 1;

    vector<vector<vector<long long>>> 
        dist_map(m, vector<vector<long long>>(n, vector<long long>(2, 0)));

    queue<Move> q;

    dist_map[0][0][0] = 1;
    dist_map[0][0][1] = 1;

    if (n > 1 && city_map[0][1] != 1)
    {
        dist_map[0][1][Dir::RIGHT] = 1;
        q.push({ 0, 1, Dir::RIGHT });
    }
    if (m > 1 && city_map[1][0] != 1)
    {
        dist_map[1][0][Dir::DOWN] = 1;
        q.push({ 1, 0, Dir::DOWN });
    }
    while (!q.empty())
    {
        auto[r, c, dir] = q.front();
        q.pop();

        int nr = r + 1;
        int nc = c + 1;

        // 우 이동의 경우
        if (nc >= n || city_map[r][nc] == 1 || (city_map[r][c] == 2 && dir == Dir::DOWN))
        {
        }
        else
        {
            if (dist_map[r][nc][Dir::RIGHT] == 0)
                q.push({ r, nc, Dir::RIGHT });
            dist_map[r][nc][Dir::RIGHT] += dist_map[r][c][dir];
            dist_map[r][nc][Dir::RIGHT] %= MOD;
        }

        // 하 이동의 경우
        if (nr >= m || city_map[nr][c] == 1 || (city_map[r][c] == 2 && dir == Dir::RIGHT))
        {
        }
        else
        {
            if (dist_map[nr][c][Dir::DOWN] == 0)
                q.push({ nr, c, Dir::DOWN });
            dist_map[nr][c][Dir::DOWN] += dist_map[r][c][dir];
            dist_map[nr][c][Dir::DOWN] %= MOD;
        }
    }

    answer = dist_map[m - 1][n - 1][RIGHT] + dist_map[m - 1][n - 1][DOWN];
    return answer % MOD;
}

시작 위치를 첫 지점으로 잡기가 애매해서 한번 이동한 (1, 0) 과 (0, 1)을 큐에 넣은 상태로 시작했습니다.

 

if 문의 시작을 저렇게 잡아서 if문안에 아무것도 없고 else문에서 진행하는 형태가 되어버렸네요

 

중요한 것은 같은 상태에 도달(dist_map[r][c][dir] != 0)이라면 q에 넣지않고 값만 계산하는 것입니다.

만약에 넣는다면 이후 값이 중복계산될 것입니다.

---

문제의 답은 맞았지만 현재 코드에는 맹점이 있습니다.

만약 특정 위치에서 경우의 수가 MOD와 같다면 0이되기 때문에 계산이 어긋날 가능성이 있습니다. 초깃값을 다르게 설정하든지 해야겠네요