[프로그래머스] 보행자 천국 (미해결)

 

---

 

 

온라인 문제풀이 사이트 Programmers의 문제 '보행자 천국' 문제.

https://programmers.co.kr/learn/courses/30/lessons/1832?language=java

 

문제는 간단하게 다음과 같다.

1. m X n 배열이 주어진다.

2. 0은 차량 통행 가능, 1은 차량 통행 불가, 2는 좌회전과 우회전 금지(진입한 방향 기준 직진만 가능)

3. (0, 0) 부터 (m, n)까지 갈 수 있는 경로의 수를 출력한다.

 

풀이 과정

m과 n의 최댓값이 500이므로, 완전탐색으로 충분히 풀 수 있는 문제이다.

result 배열을 만들어 오른쪽과 아래쪽 방향으로 수를 채워 나갈 것이다.

현재 index가 최상단과 가장 좌측일 경우, 진입한 경로가 하나이기 때문에 1로 채운다.

 

주어진 배열에 따라 아래 그림과 같이 각 index 값을 조정한다

 

 

이제 나머지 index를 아래와 같이 채운다

 

실행 결과 두 개의 테스트 케이스가 맞은 것을 확인 할 수 있었는데,
실제로 채점을 해 보니 채점은 하나의 테스트 케이스이며 실패가 떴다.

 

아래는 코드 전문

class Solution{
  static int MOD = 20170805;
  public static int solution(int m, int n, int[][] cityMap) {
      int answer = 0;
      int [][] resultArr = new int[m][n];
      
      for(int i = 0; i < m; i++) {
          for(int j = 0; j < n; j++){
              resultArr[i][j] = 1;
          }
      }
      
      for(int i = 0; i < m; i++){
          for(int j = 0; j < n; j++){
              
              switch(cityMap[i][j]) {
              
              case 0 :
                  if(i > 0 && j > 0) resultArr[i][j] = (resultArr[i-1][j] % MOD + resultArr[i][j-1] % MOD) % MOD;
                  else resultArr[i][j] = 1;
                  break;
                  
              case 1 :
                  resultArr[i][j] = 0;
                  break;
                  
              case 2 :
                  if(i > 0 && j > 0) resultArr[i][j] = (resultArr[i-1][j] % MOD + resultArr[i][j-1] % MOD) % MOD;
                  if(resultArr[i][j] > 0) resultArr[i][j] -= 1;
                  break;
              }
          }
      }
      
      answer = resultArr[m-1][n-1] % MOD;
      
      return answer;
  }
}
 

해설을 참고하니 로직 상으로 틀린 것 같지는 않은데, 

어디서 잘못됐는지 확인 중이다.

현재 생각으로는 아마도 값의 범위에서 오류가 나는 듯 하다.