알고리즘 여러 조건의 격자 경로 알고리즘

김정훈·2024년 4월 4일

일반적인 격자 최단 경로 알고리즘은 point[x][y-1] + point[x-1][y]를 이용해서 경로를 계산합니다. 하지만 가지말아야 할 장소와 반드시 거쳐가야 하는 장소가 있다면 어떨까요?

일반적인 알고리즘의 원리

격자 알고리즘을 다룰 때의 조건은 각각의 x축과 y축에 대해서 오직 한 방향으로만 이동해야 하는 것입니다.

이 경우에는 오른쪽과 아래쪽으로만 이동할 수 있습니다. R과 D로 표현하자면 목적지로 가기 위해선 RRRRDDD로 이동하면 되겠네요. 이 때 순서는 상관이 없기 때문에 7번의 이동에서 경로를 마음대로 가면 되는 겁니다. 때문에 조합(Combinamtion)으로도 문제를 해결할 수 있습니다. 조합 문제이기 때문에 point[x][y-1] + point[x-1][y] 알고리즘 역시 성립합니다.

조건이 있는 격자

위의 격자에 가면 안되는 지점에 x, 반드시 거쳐야하는 지점의 후보군에 o 표시가 있다고 생각해보면 복잡해집니다. 이 조건에서 o 지점을 k번 이상 반드시 거쳐야 한다고 가정합시다.

x를 만난 경우

x를 만났다면 그 지점의 값은 0으로 처리되어 무시하게 됩니다.

o를 n번 지난경우

일반 지점을 지나면 똑같이 counting 하면 됩니다. 이 때 o를 만나기 전의 경우의 수 이므로 o를 0회 방문한 경우가 됩니다. o를 처음 만났다면 이는 o를 1회 방문한 경우가 됩니다. 즉 이제껏 counting 한 경우의 수가 10이라면 o를 방문한 순간부터 다음 경로는 0/10이 됩니다.
이 이후의 경로는 o를 만나기 전까지 n/10으로 카운트 됩니다. 그러다 또 o를 만나게 되면 카운트이 경우가 바뀌게 되고 최종적으로는
업로드중..
이와 같은 counting 목록이 만들어 집니다. k회 이상은 (k-1)회와 k회에서의 경우를 더해준 다음 업데이트 하면 됩니다. 이 때 point[x][y-1] + point[x-1][y]은 각각의 o 방문 횟수들끼리 더해주면 됩니다. 쉽게 말해 0회+0회/1회+1회/..... 가 됩니다.

설명이 다소 부족한데 텍스트로 표현하기가 참 어렵네요... 코드를 살펴보겠습니다.

코드 설명

point 클래스

class Point {
    int valueArr[], judge;
    Point(int arrSize, int judge) {
        this.valueArr = new int[arrSize + 1];
        this.judge = judge;
    }

judge 0이면 x 지점, 1이면 일반지점, 2이면 o 지점입니다. 각각의 경로의 수를 배열로 관리합니다.

shifiting 메소드

void normalShifting() {
        int size = valueArr.length;
        if(size>=2) {
            valueArr[size - 1] = (valueArr[size - 1] % 1000000007 + valueArr[size - 2] % 1000000007)%1000000007;
            for (int k = size - 2; k > 0; k--) {
                valueArr[k] = valueArr[k - 1];
            }
            valueArr[0] = 0;
        }
    }

각 경우의 수를 다음 경우로 이동시키기 위한 메소드입니다. 0번 인덱스는 무조건 0으로 초기화 됩니다.

add shifting

  void addShifting(int[] arr1, int[] arr2) {
       add(arr1,arr2);
       normalShifting();
   }
   void add(int[] arr1, int[] arr2) {
       for (int n = 0; n < valueArr.length; n++) {
           valueArr[n] = (arr1[n]%1000000007 + arr2[n]%1000000007)%1000000007;
       }
   }