[Lv3] 보행자 천국

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

보행자 천국

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

• 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
• 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
• 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

예제 입출력

m	n	city_map	answer
3	3	[[0, 0, 0], [0, 0, 0], [0, 0, 0]]	6
3	6	[[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]]	2

예제에 대한 설명

첫 번째 예제는 모든 도로가 제한 없이 통행 가능한 경우로, 가능한 경우의 수는 6가지이다.
두 번째 예제는 문제 설명에 있는 그림의 경우이다. 가능한 경우의 수는 빨간 실선과 노란 점선 2가지뿐이다.

 

 

---

 

이전에 푼 문제와 유사한 패턴입니다.

[Problem Solving/programmers] - [Lv3] 등굣길

 

장애물은 같지만, 오던 진행방향으로만 진행되는 방향고정구간이 추가되었습니다.

 

숫자가 아주 커지므로 항상 MOD=20170805로 나눈 나머지를 저장합니다.

 

 

기존 방식으로 풀어봤습니다.

public static int solution(int m, int n, int[][] cityMap) {
    for(int i=0;i<cityMap.length;i++) {
        for(int j=0;j<cityMap[0].length;j++) {
            cityMap[i][j]*=-1;
        }
    }
    for(int i=1;i<cityMap[0].length;i++) {
        if(cityMap[0][i]==-1) break;
        if(cityMap[0][i]==0) cityMap[0][i]=1;
    }
    for(int i=1;i<cityMap.length;i++) {
        if(cityMap[i][0]==-1) break;
        if(cityMap[i][0]==0) cityMap[i][0]=1;
    }
    for(int i=1;i<cityMap.length;i++) {
        for(int j=1;j<cityMap[0].length;j++) {
            if(cityMap[i][j]==-2) {
                int index = i+1;
                if(cityMap[i-1][j]>0) {
                    while(true) {
                        if(index==cityMap.length) break;
                        else {
                            if(cityMap[index][j]==-2) index++;
                            else if(cityMap[index][j]==-1) break;
                            else {
                                cityMap[index][j]=(cityMap[index][j]+cityMap[i-1][j])%MOD;
                                break;
                            }
                        }
                    }
                }
                if(cityMap[i][j-1]>0) {
                    index = j+1;
                    while(true) {
                        if(index==cityMap[0].length) break;
                        else {
                            if(cityMap[i][index]==-2) index++;
                            else if(cityMap[i][index]==-1) break;
                            else {
                                cityMap[i][index]=(cityMap[i][index]+cityMap[i][j-1])%MOD;
                                break;
                            }
                        }
                    }
                }
            } else if(cityMap[i][j]==0) {
                if(cityMap[i-1][j]<0 && cityMap[i][j-1]<0) {}
                else if(cityMap[i-1][j]<0) {
                    if(cityMap[i][j-1]>0) cityMap[i][j]=cityMap[i][j-1];
                } else if(cityMap[i][j-1]<0) {
                    if(cityMap[i-1][j]>0) cityMap[i][j]=cityMap[i-1][j];
                } else {
                    cityMap[i][j]=(cityMap[i-1][j]+cityMap[i][j-1])%MOD;
                }
            } else if(cityMap[i][j]>0) {
                if(i-1>=0 && cityMap[i-1][j]<0 && j-1>=0 && cityMap[i][j-1]<0) {}
                else if(i-1>=0 && cityMap[i-1][j]<0) {
                    if(cityMap[i][j-1]>0) cityMap[i][j]=(cityMap[i][j]+cityMap[i][j-1])%MOD;
                }
                else if(j-1>=0 && cityMap[i][j-1]<0) {
                    if(cityMap[i-1][j]>0) cityMap[i][j]=(cityMap[i][j]+cityMap[i-1][j])%MOD;
                }
            }
        }
    }
    int result = cityMap[cityMap.length-1][cityMap[0].length-1];
    if(result==-2) {
        result = 0;
        int index = cityMap.length-2;
        while(index>=0) {
            if(cityMap[index][cityMap[0].length-1]==-2) index--;
            else if(cityMap[index][cityMap[0].length-1]==-1) break;
            else result = cityMap[index][cityMap[0].length-1];
        }
        index = cityMap[0].length-2;
        while(index>=0) {
            if(cityMap[cityMap.length-1][index]==-2) index--;
            else if(cityMap[cityMap.length-1][index]==-1) break;
            else result = (result+cityMap[cityMap.length-1][index])%MOD;
        }
        return result;
    } else return result;
}

여전히 -1은 장애물로, 이번엔 -2를 방향고정구간으로 했습니다.

-1을 만나면 아무것도 안하고,

-2를 만나면 -2들을 넘어서 그 위치에 미리 자기 값을 더해둡니다.

0을 만나면 왼쪽이나 위쪽이 양수인 값들을 가져와서 합칩니다.

양수를 만나면 이미 -2로 값이 쓰여진 상태입니다. 왼쪽이나 위 중 양수인 값들을 가져와서 마저 합칩니다.

 

기존 풀이법으로는 -2나 -1은 직접 건드리지 않기 때문에 특수구간은 특수구간인 채로 남습니다.

혹시 마지막 구하는 곳이 -2일 경우(그래도 도달은 가능하니),

-2를 반환하지 않기 위해 특별히 result를 구해서 다시 검증합니다.

 

긴 예제에 대하여 맵과 결과값은 다음과 같습니다.

 

[0, -2, 1, 1, 1, -2, 1, 1, 1, 1, 1, 1, -2, 1, 1, 1, -2, 1, 1, 1, 1, 1, 1, -2, 1, 1, 1, -2, 1, 1, 1, 1, 1, 1]
[1, 1, -2, 2, -1, 0, 1, 2, -1, 1, 2, 3, 3, -2, 4, -1, 0, 1, 2, -1, 1, 2, 3, 3, 4, -2, 5, 5, -1, 1, 2, -2, -2, 3]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 2, -1, 3, 6, 7, -2, 7, 7, 8, 10, 10, -2, -2, 13, 16, -1, 1, 6, 11, 11, 12, 14, 15, 16, 19]
[0, 1, -2, 1, -1, 0, 1, 3, -1, 2, 2, 5, 11, -2, 15, -1, 7, 15, 25, -1, 1, 3, 16, 32, 32, -2, 38, 49, -1, 12, 26, -2, -2, 45]
[0, 1, -2, 2, -1, 0, 1, 4, -1, 2, 4, 9, 20, -2, 35, -1, 7, 22, 47, -1, 1, 4, 20, 52, 84, -2, 122, 171, -1, 12, 38, -2, -2, 83]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 3, -1, 9, 29, 36, -2, 36, 43, 65, 112, 112, -2, -2, 132, 184, -1, 1, 123, 294, 294, 306, 344, 359, 375, 458]
[0, 1, -2, 1, -1, 0, 1, 5, -1, 3, 3, 12, 41, -2, 76, -1, 43, 108, 220, -1, 1, 5, 137, 321, 321, -2, 444, 738, -1, 306, 650, -2, -2, 1108]
[0, 1, -2, 2, -1, 0, 1, 6, -1, 3, 6, 18, 59, -2, 135, -1, 43, 151, 371, -1, 1, 6, 143, 464, 785, -2, 1229, 1967, -1, 306, 956, -2, -2, 2064]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 4, -1, 18, 77, 113, -2, 113, 156, 307, 678, 678, -2, -2, 821, 1285, -1, 1, 1230, 3197, 3197, 3503, 4459, 4818, 5193, 7257]
[-1, 1, -2, -1, -2, 0, 1, -2, 2, 6, -1, 18, 95, 208, -2, 321, 477, 784, 1462, 2140, -2, -2, 2961, 4246, -1, 1, 1231, 4428, 7625, 11128, 15587, 20405, 25598, 32855]
[0, 1, -2, 1, -1, 0, 1, 7, -1, 6, 6, 24, 119, -2, -2, -1, 477, 1261, 2723, -1, 1, 7, 2968, 7214, 7214, -2, 8445, 12873, -1, 11128, 26715, -2, -2, 59570]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 7, -1, 24, 143, 351, -2, 351, 828, 2089, 4812, 4812, -2, -2, 7780, 14994, -1, 1, 8446, 21319, 21319, 32447, 59162, 79567, 105165, 164735]
[0, 1, -2, 1, -1, 0, 1, 8, -1, 7, 7, 31, 174, -2, -2, -1, -2, -2, 4812, -1, 1, 8, 7788, 22782, 22782, -2, 31228, 52547, -1, 32447, 91609, -2, -2, 256344]
[-1, 1, 2, -2, -2, -1, 1, 9, 9, -2, 16, 47, 221, -2, 356, -1, 828, 2917, 7729, -1, 1, 9, 7797, -1, -2, 1, 31229, 83776, 83776, 116223, 207832, 287399, 392564, 648908]
[0, 1, -2, 2, -1, 0, 1, 10, -1, 7, 23, 70, 291, -2, 647, -1, 828, 3745, 11474, -1, 1, 10, 7807, 7807, 30589, -2, 61818, 145594, -1, 116223, 324055, -2, -2, 972963]
[0, 1, -2, 3, -1, 0, 1, 11, -1, 7, 30, 100, 391, -2, 1038, -1, 828, 4573, 16047, -1, 1, 11, 7818, 15625, 46214, -2, 108032, 253626, -1, 116223, 440278, -2, -2, 1413241]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 8, -1, 100, 491, 842, -2, 842, 1670, 6243, 22290, 22290, -2, -2, 30108, 45733, -1, 1, 108033, 361659, 361659, 477882, 918160, 1205559, 1598123, 3011364]
[-1, 1, -2, -1, -2, 0, 1, -2, 2, 10, -1, 100, 591, 1433, -2, 2275, 3945, 10188, 32478, 54768, -2, -2, 84876, 130609, -1, 1, 108034, 469693, 831352, 1309234, 2227394, 3432953, 5031076, 8042440]
[0, 1, -2, 1, -1, 0, 1, 12, -1, 10, 10, 110, 701, -2, 1739, -1, 3945, 14133, 46611, -1, 1, 12, 84888, 215497, 215497, -2, 323531, 793224, -1, 1309234, 3536628, -2, -2, 11579068]
[-1, 1, -2, -1, -2, 0, 1, -2, 1, 11, -1, 110, 811, 2244, -2, 2244, 6189, 20322, 66933, 66933, -2, -2, 151821, 367318, -1, 1, 323532, 1116756, 1116756, 2425990, 5962618, 9395571, 14426647, 5834910]
[-1, 1, 3, 3, 3, 3, 4, 16, 17, 28, 28, 138, 949, 3193, -2, 5437, 11626, 31948, 98881, 165814, 165815, 165827, 317648, 684966, 684966, 684967, 1008499, 2125255, 3242011, 5668001, 11630619, 855385, 15282032, 946137]
답: 946137

 

 

이 경우도 값이 계속 커져서 나누는 값으로 여러번 나머지로 계산된 결과인데, 케이스 검증에서는 값이 틀렸다고 합니다.

 

대체 어디서 수가 틀어지는지 알 수가 없으니..

 

이번엔 방향고정구간이 추가됨에 따라

 

왼쪽에서 올 수 있는 경우의 맵과 위에서 올 수 있는 경우의 맵을 두가지로 나눠서 작성합니다.

public int solution(int m, int n, int[][] cityMap) {
    int[][] byLeft = new int[cityMap.length][cityMap[0].length];
    int[][] byUp = new int[cityMap.length][cityMap[0].length];
    for(int i=1;i<cityMap[0].length;i++) {
        if(cityMap[0][i]!=1) byLeft[0][i] = 1;
        else break;
    }
    for(int i=1;i<cityMap.length;i++) {
        if(cityMap[i][0]!=1) byUp[i][0] = 1;
        else break;
    }
    for(int i=1;i<cityMap.length;i++) {
        for(int j=1;j<cityMap[0].length;j++) {
            if(cityMap[i][j]!=1) {
                byUp[i][j]=byUp[i-1][j];
                if(cityMap[i-1][j]!=2) byUp[i][j]=(byUp[i][j]+byLeft[i-1][j])%MOD;
                byLeft[i][j]=byLeft[i][j-1];
                if(cityMap[i][j-1]!=2) byLeft[i][j]=(byLeft[i][j]+byUp[i][j-1])%MOD;
            }
        }
    }
    return (byUp[cityMap.length-1][cityMap[0].length-1]+byLeft[cityMap.length-1][cityMap[0].length-1])%MOD;
}

맨 위의 행에 대하여 오른쪽으로만 움직일 수 있으니, ByLeft를 장애물을 만나기 전까지 1로 기록합니다.

맨 첫 열에 대하여 아래로만 움직일 수 있으니, ByUp을 장애물을 만나기 전까지 1로 기록합니다.

 

이제 1,1부터 마지막,마지막까지 기록합니다.

 

장애물이 아니라면(!=-1) 기록할텐데,

 

우선 ByUp은 위에서 그대로 가져올 수 있고, ByLeft도 왼쪽에서 그대로 가져올 수 있습니다.

(어차피 장애물이면 0일테니)

 

위쪽이 2가 아니라면 위쪽에 ByLeft로 도달한 경우도 꺾어서 내려올 수 있을테니 더해줍니다.

왼쪽이 2가 아니라면 왼쪽에 ByUp으로 도달한 경우도 꺾어서 옆으로 올 수 있을테니 더해줍니다.

 

마지막엔 마지막칸에 ByLeft와 ByUp으로 올 수 있는 경우를 더해서 반환합니다.

아래는 기존방식의 예제와 같은 예제를 맵과 결과로 출력했습니다.

 

 

[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 0, 0, 1, 2, 0, 1, 2, 3, 3, 4, 4, 0, 0, 1, 2, 0, 1, 2, 3, 3, 4, 5, 5, 5, 0, 1, 2, 3, 3, 3]
[0, 1, 2, 0, 0, 0, 1, 3, 1, 2, 0, 3, 6, 7, 11, 7, 7, 8, 10, 10, 11, 12, 13, 16, 0, 1, 6, 11, 11, 12, 14, 15, 16, 19]
[0, 1, 2, 1, 0, 0, 1, 3, 0, 2, 2, 5, 11, 18, 15, 0, 7, 15, 25, 0, 1, 3, 16, 32, 32, 33, 38, 49, 0, 12, 26, 41, 42, 45]
[0, 1, 2, 2, 0, 0, 1, 4, 0, 2, 4, 9, 20, 27, 35, 0, 7, 22, 47, 0, 1, 4, 20, 52, 84, 85, 122, 171, 0, 12, 38, 53, 54, 83]
[0, 1, 2, 0, 0, 0, 1, 5, 1, 3, 0, 9, 29, 36, 71, 36, 43, 65, 112, 112, 113, 116, 132, 184, 0, 1, 123, 294, 294, 306, 344, 359, 375, 458]
[0, 1, 2, 1, 0, 0, 1, 5, 0, 3, 3, 12, 41, 77, 76, 0, 43, 108, 220, 0, 1, 5, 137, 321, 321, 322, 444, 738, 0, 306, 650, 1009, 1025, 1108]
[0, 1, 2, 2, 0, 0, 1, 6, 0, 3, 6, 18, 59, 95, 135, 0, 43, 151, 371, 0, 1, 6, 143, 464, 785, 786, 1229, 1967, 0, 306, 956, 1315, 1331, 2064]
[0, 1, 2, 0, 0, 0, 1, 7, 1, 4, 0, 18, 77, 113, 248, 113, 156, 307, 678, 678, 679, 684, 821, 1285, 0, 1, 1230, 3197, 3197, 3503, 4459, 4818, 5193, 7257]
[0, 1, 2, 0, 0, 0, 1, 7, 2, 6, 0, 18, 95, 208, 343, 321, 477, 784, 1462, 2140, 2141, 2146, 2961, 4246, 0, 1, 1231, 4428, 7625, 11128, 15587, 20405, 25598, 32855]
[0, 1, 2, 1, 0, 0, 1, 7, 0, 6, 6, 24, 119, 327, 254, 0, 477, 1261, 2723, 0, 1, 7, 2968, 7214, 7214, 7215, 8445, 12873, 0, 11128, 26715, 47120, 52313, 59570]
[0, 1, 2, 0, 0, 0, 1, 8, 1, 7, 0, 24, 143, 351, 486, 351, 828, 2089, 4812, 4812, 4813, 4819, 7780, 14994, 0, 1, 8446, 21319, 21319, 32447, 59162, 79567, 105165, 164735]
[0, 1, 2, 1, 0, 0, 1, 8, 0, 7, 7, 31, 174, 525, 309, 0, 828, 2089, 4812, 0, 1, 8, 7788, 22782, 22782, 22783, 31228, 52547, 0, 32447, 91609, 171176, 196774, 256344]
[0, 1, 2, 3, 2, 0, 1, 9, 9, 16, 16, 47, 221, 572, 356, 0, 828, 2917, 7729, 0, 1, 9, 7797, 0, 22782, 1, 31229, 83776, 83776, 116223, 207832, 287399, 392564, 648908]
[0, 1, 3, 2, 0, 0, 1, 10, 0, 7, 23, 70, 291, 642, 647, 0, 828, 3745, 11474, 0, 1, 10, 7807, 7807, 30589, 30590, 61818, 145594, 0, 116223, 324055, 611454, 716619, 972963]
[0, 1, 3, 3, 0, 0, 1, 11, 0, 7, 30, 100, 391, 742, 1038, 0, 828, 4573, 16047, 0, 1, 11, 7818, 15625, 46214, 46215, 108032, 253626, 0, 116223, 440278, 727677, 832842, 1413241]
[0, 1, 3, 0, 0, 0, 1, 12, 1, 8, 0, 100, 491, 842, 1880, 842, 1670, 6243, 22290, 22290, 22291, 22301, 30108, 45733, 0, 1, 108033, 361659, 361659, 477882, 918160, 1205559, 1598123, 3011364]
[0, 1, 3, 0, 0, 0, 1, 12, 2, 10, 0, 100, 591, 1433, 2471, 2275, 3945, 10188, 32478, 54768, 54769, 54779, 84876, 130609, 0, 1, 108034, 469693, 831352, 1309234, 2227394, 3432953, 5031076, 8042440]
[0, 1, 3, 1, 0, 0, 1, 12, 0, 10, 10, 110, 701, 2134, 1739, 0, 3945, 14133, 46611, 0, 1, 12, 84888, 215497, 215497, 215498, 323531, 793224, 0, 1309234, 3536628, 6969581, 8567704, 11579068]
[0, 1, 3, 0, 0, 0, 1, 13, 1, 11, 0, 110, 811, 2244, 3983, 2244, 6189, 20322, 66933, 66933, 66934, 66945, 151821, 367318, 0, 1, 323532, 1116756, 1116756, 2425990, 5962618, 9395571, 14426647, 5834910]
[0, 1, 3, 3, 3, 3, 4, 16, 17, 28, 28, 138, 949, 3193, 4932, 5437, 11626, 31948, 98881, 165814, 165815, 165827, 317648, 684966, 684966, 684967, 1008499, 2125255, 3242011, 5668001, 11630619, 855385, 15282032, 946137]

답: 946137

 

 

기막히게 같지만, 어느 구간에서는 틀어지겠지요. 코드와 컴퓨터는 거짓말을 하지 않으니.

 

 

길찾기 문제는 기존 맵에 그대로 푸는 것이 아니라, 경우의수 맵을 따로 작성하여 풀 것.

방향고정 구간이 생긴다면 가로와 세로 움직임에 대한 경우의수 맵을 각각 작성하여 마지막에 합칠 것.