[알고리즘 깨알팁] 재귀로 1, 2차원 구간 처리하기

가끔가다 for문만으로는 문제를 처리하기 힘든 경우가 있습니다.

대표적인 경우가 2차원 배열에 대한 순열을 만들어야 하는 경우이죠.

자, 이럴때 여러분은 어떻게 해결하십니까!?

음.. 다른 분들도 편하게 느끼실진 모르겠지만, 제가 사용하는 방법을 알려드리려고 합니다!

우선, 일차원 배열에서 재귀 함수를 어떻게 작성하는지 생각해봅시다.

이렇게, 4개의 배열이 있으면, 위와 같이 0번 인덱스를 처리 후 1번 인덱스, 2번 인덱스, ... 마지막인덱스를 확인한 후에

기저사례로 모두 검색한 다음 이전 인덱스로 돌아갑니다!

즉, 현재 인덱스를 처리한 후 다음 인덱스를 처리한다.

마지막 인덱스까지 다 봤으면 return한다.

이 처리입니다!

1차원 배열에서는 다음 인덱스는 그냥 현재 인덱스 + 1 입니다.

코드로 나타내면 다음과 같죠.

void dfs(int i){
    if(i == n){
        //process..
        return;
    }
 
    //process..
 
    dfs(i+1);
 
    //process.. 
}

그럼 2차원에서는 어떨까요???

2차원 배열도 마찬가지입니다!

현재 좌표를 처리한 후 다음 좌표를 처리한다.

마지막 좌표까지 다 봤으면 return한다.

for문을 생각해보시면 됩니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        printf("%d %d\n", i, j);        
    }
    printf("\n");
}
 

간단한 코드입니다!

그림으로 처리되는 순서를 봅시다.

3행 3열 (일반화로는 n행 m열)

위 그림을 보면, (0,0) -> (0,1) -> (0,2) 로 처리됩니다.

즉, 현재 좌표가 r,c라면, 다음 좌표로 가는 방법은 (r, c+1) 이었던 것입니다!

하지만... 2차원의 경우엔 아래 그림과 같이 행이 변경되는 구간이 있죠.

행이 바뀌어야 하는순간!

그것은 바로 c가 m이 되는 순간입니다!

즉, next = (r,c+1)이라고 우선 만들어 두고,

c+1 == m이 된다면 next를 (r+1,0)으로 바꾸면 되는 것 입니다!

그렇다면, 기저 사례는 언제일까요??

마지막 좌표란, 모든 2차원 구간을 탐색한 후이죠.

즉, 다음과 같은 경우죠!

r이 n이 되는 순간! 그 때가 바로 return이 되어야 하는 순간입니다.

코드로 템플릿을 보여드리면..

void dfs(int r, int c){
    if(r == n){
        //process..
        return;
    }
 
    int nr = r;
    int nc = c+1;
 
    if(nc == m){
        ++nr, nc = 0;
    }
 
    //process..
 
    dfs(nr,nc);
    
    //process;
}
 

짜라잔~ 이렇게 되겠죠!