유형 _ 재귀로 분할정복 | 백준 1992번 쿼드트리 [C++]

0. 문제

https://www.acmicpc.net/problem/1992

 

 

---

1. 문제풀이 핵심

 

[핵심 아이디어] 

작게 쪼개지며 반복되는 패턴을 찾아 재귀 함수로 구현하는 것이 핵심입니다.

 

[반복되는 패턴]

1. 현재 구역 전체를 훑는다.

2. 서로 다른 숫자가 나오면 현재 구역을 4등분(재귀 호출)한다.

3. 모두 같은 숫자이면, 해당 숫자로 압축하여 반환한다.

 

 

[종료 조건]

재귀의 종료 조건은 len == 1인 최소 단위가 됩니다. 

 

 

 

---

2. 문제풀이에 사용된 개념

[알고리즘 풀이 규칙]

로직이 반복되는 경우(+ 매개변수가 바뀌는 경우)에는, 재귀함수를 짭니다.

 

[재귀 구현 방법]

재귀를 어떻게 구현할 것인지에 대해 2가지 방법이 있습니다.

전체 코드 중 주요 로직을 sudo 코드 형식으로 작성하여 두 방식의 구조 차이를 간단히 보겠습니다. 전체 코드는 아래 3. 문제풀이 코드 에 있습니다. 

 

1. 문자열 반환 방식

재귀적으로 문자열을 만들어 반환하며, 반환된 문자열을 조합해서 최종 결과를 얻습니다.

 

[sudo 코드]

//재귀함수
for i = x -> x + length - 1:
    for j = y -> y + length - 1:
    	if board[i][j] is not cur:
            res+='(';
            res+=재귀함수(x,y,len);
            res+=')';
            return res;

return cur; //cur = board[x][y]

//main 함수
cout << 재귀함수(0,0,n);

 

 

2. cout을 이용한 실시간 출력 방식

재귀적으로 함수를 호출하며 중간에 결과를 바로바로 출력합니다. 재귀 함수는 별도의 값을 반환하지 않습니다.

[sudo 코드]

//재귀함수
for i = x -> x + length - 1:
    for j = y -> y + length - 1:
    	if board[i][j] is not cur:
            cout << '(';
            재귀함수();
            cout << ')';
            return;
            
cout << cur; //cur=board[x][y]
return;

//main 함수
재귀함수(0,0,n);

 

 

---

3. 문제풀이 코드

1. 문자열 반환 방식

#include<bits/stdc++.h>

using namespace std;

int n; //행,열 
char board[65][65];

int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};

string recurFunc(int x,int y, int len){
    char cur = board[x][y];
    string res = "";

    for(int i=x; i<x+len; i++){
        for(int j=y; j<y+len; j++){
            if(board[i][j] != cur){ //현재 영역에서 서로 다른숫자가 나온경우
                len /= 2;
                res += '(';
                
                for(int dir =0; dir <4; dir++){ //4분할
                    int nx = x + dx[dir]*len;
                    int ny = y + dy[dir]*len;
                    
                    res += recurFunc(nx,ny,len);
                }   
                res += ')';
                return res;
            }
        }
    }
    return string(1,cur);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    
    scanf("%d", &n);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf(" %c", &board[i][j]);
        }
    }

    cout << recurFunc(0,0,n);
}

 

2. cout을 이용한 실시간 출력 방식

#include<bits/stdc++.h>

using namespace std;

int n; //행,열 
int board[65][65];

int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};

void recurFunc(int x,int y, int len){
    int cur = board[x][y];

    for(int i=x; i<x+len; i++){
        for(int j=y; j<y+len; j++){
            if(board[i][j] != cur){ //현재 영역에서 서로 다른숫자가 나온경우
                len /= 2;
                cout << '(';
                
                for(int dir =0; dir <4; dir++){ //4분할
                    int nx = x + dx[dir]*len;
                    int ny = y + dy[dir]*len;
                    
                    recurFunc(nx,ny,len); 
                }
                cout << ')';
                return;       
            }
        }
    }
    cout << cur;
    return;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    
    scanf("%d", &n);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%1d", &board[i][j]);
        }
    }

    recurFunc(0,0,n);
}

 

3-1. 코드 로직 설명

1. 문제풀이 핵심 에서 본 [반복되는 패턴] 과 같습니다. 

1.   현재 구역 전체를 훑는다

2-1. 다른 숫자가 나오면, 현재 구역을 4등분한다(= 재귀호출).

2-2. 모두 같은 숫자이면, 해당 숫자로 압축한다.

 

이 과정을 재귀로 구현하고, main 함수에서 재귀함수를 호출하여 사용합니다. 

 

이때 재귀함수인데, 종료조건을 붙이지 않은 것을 알 수 있습니다. 

왜냐하면 코드를 짜며 생각해보니... 종료조건이 필요한 부분인 최소단위 한칸(len=1)에 대한 재귀함수가 호출되었을 때, 이 함수가 len=0인 재귀함수를 호출하는 일은 없습니다.

왜냐면, 한칸에서는 len==1이므로 이중 for문이 실행되지 않습니다. 그래서 종료조건을 붙이지 않았습니다. 그러나, 일반 재귀함수에서 종료조건은 필수적인 사항이니, 습관적으로 붙이는 것도 좋을 것 같습니다.

 

다음은 재귀함수 맨 위에 들어갈 종료조건 형태입니다.

//첫번째 코드에서의 종료조건 형태
if(len == 1){
    return board[x][y]; // 이떄, board[x][y] = 현재 영역의 공통된 숫자
}

//두번째 코드에서의 종료조건 형태
if(len == 1){
    cout << cur; // 이때, cur = board[x][y] 
    return;
}

---

 

4. 문제풀이에 사용된 함수

string(1,cur);

• 이 구문은 cur라는 char를 길이가 1인 string으로 변환합니다.
• 사용 이유: 함수의 반환 자료형이 string이기 때문입니다.

왜 함수의 자료형이 string인가?

• 재귀 함수는 문자열을 쌓아가면서 결과를 만들어 내는 역할을 합니다.
• 쌓아온 문자열을 최종 결과로 반환해야 하기 때문에, 함수의 반환 자료형은 string이 됩니다.
• 따라서 함수가 최종적으로 반환하는 값이 string이어야 하며, 모든 반환값은 string으로 맞춰야 합니다.

재귀 함수에서 char를 string으로 변환하는 이유

• 재귀 함수의 구조 상, 현재 영역의 모든 값이 동일하다면 하나의 문자(char)를 반환해야 합니다.
• 하지만 함수의 반환값은 string이어야 하기 때문에, char를 string으로 변환하여 반환할 필요가 있습니다.
• 이때 사용하는 방법이 string(1, s);로, s라는 char를 길이가 1인 string으로 변환하여 반환할 수 있게 됩니다.

string(자릿수, 변수명);

• 주어진 char를 특정 길이의 문자열로 변환하는 방법입니다.
• 재귀 함수에서 최종적으로 문자열을 반환해야 하는 상황에서 유용하게 사용됩니다.

** 별개로, string에는 char를 바로 더할 수 있습니다. 

 

---

 

5. 요약 정리

1. 반복되는 로직이고, 들어가는 숫자만 달라진다 -> 재귀 함수 사용
   • 동일한 패턴의 작업이 반복되면서 매개변수만 변화할 때, 재귀 함수를 이용해 효율적으로 구현할 수 있습니다.
2. 전체를 일부로 나눠서 합산하는 방식이다 -> 분할정복
   • 문제를 작은 부분으로 나누어 각각 해결한 후 합쳐서 최종 답을 구하는 방법입니다.
   • 분할 정복의 형태:
     • res += 재귀함수(); 처럼, 재귀 함수의 반환값을 이용해 값을 합해나가는 방식입니다.
3. 재귀 함수 형태
   • 값을 쌓아가서 최종적으로 결과값을 반환하는 구조로 되어 있습니다.
   • 재귀 함수에서 문자열을 쌓아줄 때, 사실 char를 직접 string에 더할 수 있습니다. 그러나 최종 결과값이 string으로 반환되어야 하므로, 최소 단위에서 char 값을 반환할 때는 이를 길이가 1인 string으로 변환해 반환하게 됩니다.

주의사항

반복되는 패턴을 찾을 때, 대충 생각하지 말고 정확히 텍스트로 작성하여 반복의 시작과 끝을 명확히 파악하는 것이 중요합니다.

• 흐릿한 개념만 가지고 코드를 짜기 시작하면 구현 중 헷갈리거나 문제가 생길 가능성이 높습니다. 사실 제가 그랬습니다...

 

 

+) 나의 문제사항

• 초기 로직 설계 시 부족했던 점
  • 처음에 로직을 짜고 들어가기는 했지만, 정확히 머리에 떠오르지 않는 세부사항은 코드짤때 생각나겠지~하며 건너뛰었습니다.
  • 이후에 구현 도중에 반복 패턴을 잘못 판단하여 한 번 틀렸습니다.
    • 잘못 생각했던 패턴 : 하나의 사각형을 탐색하고 -> 서로 다른 값이 있으면 4등분 -> 각 사분면을 탐색 -> 서로 다른 값이 있으면 또 4등분... 의 반복
• 사각형을 바로 4등분한다고 생각했던 실수
  • 처음부터 바로 사분할할 것이라고 잘못 이해하고 있었으나, 사실은 먼저 현재 사각형을 훑고, 모든 값이 동일할 때만 압축해야 했습니다.
• 이중 for문 구조에 대해 지레짐작함
  • 이중 for문 안에 또 다른 for문이 들어가는 구조를 보고 잘못된 것 아닌가 생각했으나, 실질적인 시간복잡도는 높지 않아서 문제가 없는 부분이었습니다. 
• 시간 복잡도를 제대로 계산하지 않음
  • 시간 복잡도를 제대로 계산하지 않으면 전략을 잘못 세울 수 있습니다. 문제를 풀기 전에 시간 제한과 입력 크기 n을 바탕으로 이 문제가 요구하는 시간 복잡도가 무엇인지 파악해야 하며, 그에 적합한 알고리즘이 무엇인지 생각해봐야 합니다.
  • 이 문제의 경우 이중 for문으로 전체 영역을 확인하고, 각 재귀 호출에서 4등분하여 재귀적으로 탐색합니다.
  • 따라서 대략적인 시간 복잡도는 O(N^2)이 됩니다.
  • 이 문제에서 N의 최댓값이 64입니다. 제한시간 1초를 기준으로 n 이 500 이하이면, 삼중 for문 로직까지 가능합니다. 따라서, 이 풀이법은 시간복잡도를 충족합니다.