프로그래머스 문제풀이 (알고리즘) - 등굣길

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

 

 

시도 1 (오답)

우측 아래로만 갈 수 있기 때문에, 완전 탐색이 아니라 동적 계획법으로 풀 수 있다고 생각함

만약 하나의 칸을 node 라고 부르고 x, y 좌표까지 모든 경로의 경우의 수를

node[y][x]라고 나타낼 때

장애물이 없다는 가정하면

// 위 노드까지 경로의 경우의 수 + 좌측 노드까지 경로의 경우의 수
node[y][x] = node[y-1][x] + node[y][x-1]

위 공식이 성립

예를 들어서 다음과 같이 경로가 있다고 할 때

 

위와 같이 풀이 할 수 있음. 따라서 다음과 같은 풀이를 작성

 

public int solution(int m, int n, int[][] puddles) {

    int[][] node = new int[n][m];

    for (int p = 0; p<puddles.length; p++) {
        int x = puddles[p][0]-1;
        int y = puddles[p][1]-1;
        node[y][x] = -1;
    }

    for (int x=0; x<m; x++)
        if (node[0][x] != -1)
            node[0][x] = 1;

    for (int y=0; y<n; y++)
        if (node[y][0] != -1)
            node[y][0] = 1;

    for (int y=1; y<n; y++)
        for (int x=1; x<m; x++) {
            if (node[y][x] != -1) {
                node[y][x] = (node[y-1][x] != - 1 ? node[y-1][x] : 0) + (node[y][x-1] != -1 ? node[y][x-1] : 0);
            }
        }

    return node[n-1][m-1] % 1000000007;
}

 

 

시도 2 (오답)

그런데 "시도 1" 방법은 치명적인 문제가 있었는데 y = 0인 지점과 x = 0인 지점을 모두 1로 채워넣고 시작한다는 점이다.

에초에 puddle 은 x = 0 또는 y = 0 인 지점에 있을 수 있기 때문에

전부 1로 채우면 안된다.

 

 

public int solution(int m, int n, int[][] puddles) {

    long[][] node = new long[n][m];
    node[0][0] = 1;

    for (int p = 0; p<puddles.length; p++) {
        int x = puddles[p][0]-1;
        int y = puddles[p][1]-1;
        node[y][x] = -1;
    }


    for (int y=0; y<n; y++)
        for (int x=0; x<m; x++) {
            if (x == 0 && y == 0)
                continue;

            if (y == 0 && node[y][x] != -1)
                node[y][x] = (node[y][x-1] != -1 ? node[y][x-1] : 0);
            else if (x == 0 && node[y][x] != -1)
                node[y][x] = (node[y-1][x] != - 1 ? node[y-1][x] : 0);
            else if (node[y][x] != -1) {
                node[y][x] = (node[y-1][x] != - 1 ? node[y-1][x] : 0) + (node[y][x-1] != -1 ? node[y][x-1] : 0);
            }
        }

    return (int)(node[n-1][m-1] % 1000000007);
}

 

위 풀이에는 문제가 있다. 가로 세로 100만 넘어가도 순식간에 데이터 범위가 int 최대 범위를 넘어가버리기 때문에 중간중간 계속 1000000007 (프로그래머스에서 제시한 숫자) 로 나누어 주어야 했는데 이 점을 간과했다.

 

시도 3 (정답)

코드를 조금 더 깔끔하게 만들기 위해서, 2차원 배열을 가로, 세로 1씩 더 키웠고 y = 0, x = 0인 node를 모두 0으로 채우고 x = 1, y = 1 인 지점부터 계산을 시작하니 다음과 같은 풀이가 나왔다.

public int solution(int m, int n, int[][] puddles) {

    int [][] node = new int [n+1][m+1];
    boolean[][] isPuddles = new boolean[n+1][m+1];
    node[1][1] = 1;

    for (int p = 0; p<puddles.length; p++)
        isPuddles[puddles[p][1]][puddles[p][0]] = true;

    for (int y=1; y<=n; y++)
        for (int x=1; x<=m; x++) {
            if (x == 1 && y == 1)
                continue;

            node[y][x] = ((!isPuddles[y-1][x] ? node[y-1][x] : 0) + (!isPuddles[y][x-1]? node[y][x-1] : 0)) % 1000000007;
        }

    return node[n][m];
}