[프로그래머스] 등굣길

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

동적계획법 문제이다. 이 문제는 수학 시간에 경로의 갯수 문제를 풀던 방식으로 해결하였다.

예시로 살펴보자.

S가 출발지점, T가 도착지점이라고 하였을 때 도착지까지 가는 경로의 수는 다음과 같이 구할 수 있다.

출발지점에서 오른쪽으로 이동하거나 아래로 이동하는 방법은 1가지밖에 없기 때문에 값을 1로 갱신해준다.

노란 지점으로 가는 방법의 수를 (2, 2) 라고 하면 (1, 2) 와 (2, 1) 에서 이동할 수 있기 때문에 (1, 2) + (2, 1)가 된다.

위와 같은 방식으로 값을 갱신하면 목적지에 도착할 수 있는 방법은 10가지가 됨을 알 수 있다.
하지만 이 문제에서는 길이 물에 잠긴 경우가 있기 때문에 해당 경로를 제외하고 탐색해줘야하므로 문제에 주어진 예시의 경우

위의 그림과 같이 되므로 4가 정답임을 알 수 있다.

코드

C++

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> map (n, vector<int>(m, 0));
    for(auto v : puddles) map[v[1]-1][v[0]-1] = -1;
    for(int i=0; i<n; i++){
        if(map[i][0] == -1) break;
        map[i][0] = 1;
    }
    for(int i=0; i<m; i++){
        if(map[0][i] == -1) break;
        map[0][i] = 1;
    }
    for(int i=1; i<n; i++){
        for(int j=1; j<m; j++){
            if(map[i][j] == -1) continue;
            int left = map[i][j-1] == -1 ? 0 : map[i][j-1];
            int up = map[i-1][j] == -1 ? 0 : map[i-1][j];
            map[i][j] = (left + up) % MOD;
        }
    }
    return map[n-1][m-1];
}

Java

class Solution {
    final int DIV = 1000000007;

    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n][m];
        for (int[] v : puddles) map[v[1] - 1][v[0] - 1] = -1;
        for (int i = 0; i < map.length; i++) {
            if (map[i][0] == -1) break;
            map[i][0] = 1;
        }

        for (int i = 0; i < map[0].length; i++) {
            if (map[0][i] == -1) break;
            map[0][i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (map[i][j] == -1) continue;
                int left = map[i][j - 1] == -1 ? 0 : map[i][j - 1];
                int up = map[i - 1][j] == -1 ? 0 : map[i - 1][j];
                map[i][j] = (left + up) % DIV;
            }
        }
        return map[n - 1][m - 1];
    }
}