[1일 1알고] 표 편집

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

프로그래머스

 

https://basaeng.tistory.com/161

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

의 하위호환 같은 문제입니다.

 

우, 하로 이동 가능하며 모든 경우의 수를 구합니다.

 

갈 수 없는 곳만 처리하며, 같은 곳을 처리할 수 없도록합니다.

 

저는 queue로 처리했지만 그냥 for문으로 순차적으로 처리해도 충분히 처리 가능할 것으로 보입니다.

 

// mxn의 크기
// 우, 하 이동을 통한 최단경로의 개수?
// 물이 잠긴 지역을 제외

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    const int MOD = 1000000007;
    vector<vector<int>> graph(n, vector<int>(m, 0));

    for (auto puddle : puddles)
    {
        graph[puddle[1] - 1][puddle[0] - 1] = -1;
    }
    graph[0][0] = 1;
    queue<pair<int, int>> q;
    if (m > 1 && graph[0][1] != -1)
        q.push({ 0, 1 });

    if (n > 1 && graph[1][0] != -1)
        q.push({ 1, 0 });

    while (!q.empty())
    {
        auto[r,c] = q.front();
        q.pop();

        if (graph[r][c] != 0)
            continue;

        int temp = 0;
        if (c - 1 >= 0 && c - 1 < m && graph[r][c - 1] != -1)
        {
            temp += graph[r][c - 1];
        }

        if (r - 1 >= 0 && r - 1 < n && graph[r - 1][c] != -1)
        {
            temp += graph[r - 1][c];
        }

        graph[r][c] = temp % MOD;

        if (r + 1 >= 0 && r + 1 < n && graph[r + 1][c] == 0)
            q.push({ r + 1, c });
        if (c + 1 >= 0 && c + 1 < m && graph[r][c + 1] == 0)
            q.push({ r, c + 1});
    }

    answer = graph[n - 1][m - 1] % MOD;
    return answer;
}