[코딩테스트] 분할과 정복(하노이탑/영역구분/트로미노 문제)

1.하노이탑 (백준 11729)

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

11729번: 하노이 탑 이동 순서

 

1) 문제

 

2) 풀이

#include <iostream>
#include <cmath>
using namespace std;
void hanoi(int num,int from,int by,int to){
    if(num==1){
        cout<<from<<" "<<to<<"\n";
    }
    if(num>1){
        hanoi(num-1,from,to,by);//n-1개를 1(from)에서 2(by)로
        hanoi(1,from,by,to);//1(from)을 3(by)으로
        hanoi(num-1,by,from,to);//n-1개를 2(by)에서 3(to)으로
    }
}
int main(){

    int num;
    cin>>num;
    cout<<pow(2,num)-1<<"\n";
    hanoi(num,1,2,3);

}

 

3) 아이디어

 

기본 아이디어(분할과 정복)

1. 1번에 쌓여있는 n-1개의 탑을 2번으로 옮긴다.

 

2. 1번에 있는 제일 큰 원판을 3번으로 옮긴다.

3. 2번에 있는 n-1개의 탑을 3번으로 옮긴다.

 

 

hanoi 재귀 함수

void hanoi(int num,int from,int by,int to){
    if(num==1){
        cout<<from<<" "<<to<<"\n";
    }
    if(num>1){
        hanoi(num-1,from,to,by);//n-1개를 1(from)에서 2(by)로//hanoi(1,1,3,2)  
        hanoi(1,from,by,to);//1(from)을 3(by)으로//hanoi(1,1,2,3)
        hanoi(num-1,by,from,to);//n-1개를 2(by)에서 3(to)으로//hanoi(1,2,1,3)
    }
}

 

매개변수)

num은 탑의 높이(원판 개수),

from은 옮기려는 원판의 시작 기둥,

to는 옮기려는 원판의 도착 기둥,

by는 from과 to를 제외한 보조 기둥이다.

 

즉, (개수,시작 기둥,보조기둥,도착 기둥)의 틀인것이다.

 

함수)

num>1 일때 기본 아이디어에 의해

hanoi(num-1,from,to,by)는 num-1개의 원판을 from값의 기둥위치에서 by값의 기둥위치로 옮긴 후,

hanoi(1,from,by,to)는 1개의 원판을 from값의 기둥위치에서 to값의 기둥위치로 옮긴다.

마지막으로, hanoi(num-1,by,from,to)는 by값의 기둥에 위치해있는 n-1개의 원판탑을 to값의 기둥위치로 옮긴다.

 

 

---

 

2. 영역구분

input)

8

1 1 0 0 0 0 1 1 
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

 

풀이)

#include <iostream>
int arr[128][128]={0,};
int white;
int gray;
using namespace std;
void function(int startX,int startY,int endX,int endY){
    cout<<"function("<<startX<<","<<startY<<","<<endX<<","<<endY<<")\n";
    int color=arr[startX][startY];
    bool isSame=true;
    for(int i=startX;i<endX;i++){
        for(int j=startY;j<endY;j++){
            if(color!=arr[i][j]){
                 isSame=false;
            }
               
        }
    }

    
    if(!isSame){//isSame이 false라면
        // cout<<"function 재귀 호출";
        int length=(endX-startX)/2;
        function(startX,startY,startX+length,startY+length);
        function(startX,startY+length,startX+length,endY);
        function(startX+length,startY,endX,startY+length);
        function(startX+length,startY+length,endX,endY);
    }
    else{//isSame이 true라면
        if(color){//color가 1이면 회색
            gray++;
        }else{//color가 0이면 하얀색
            white++;
            
        }
    }

    return;
}

int main(){
    int num;
    cin>>num;
    for(int i=0;i<num;i++){
        for(int j=0;j<num;j++){
            cin>>arr[i][j];
        }
    }
    
    function(0,0,num,num);
    cout<<"wht?";
    cout<<white<<"\n"<<gray;
}

 

아이디어)

기본 세팅

 

function 함수에서 4조각으로 나누어서 4가지 function을 재귀호출한다.

영역에 들어있는 숫자가 모두 1 또는 모두 0 이 아니라면 영역을 더 나누어야 하므로

function함수에서 4조각으로 나누어서(1,2,3,4) 4가지 function을 재귀호출한다.

    if(!isSame){//isSame이 false라면
        // cout<<"function 재귀 호출";
        int length=(endX-startX)/2;
        function(startX,startY,startX+length,startY+length);
        function(startX,startY+length,startX+length,endY);
        function(startX+length,startY,endX,startY+length);
        function(startX+length,startY+length,endX,endY);
    }

 

function 호출되는 순서 살펴보기

 

input

 

function 호출과정

 

다른풀이)

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > arr({
	vector<int>({ 1, 1, 0, 0, 0, 0, 1, 1 }),
	vector<int>({ 1, 1, 0, 0, 0, 0, 1, 1 }),
	vector<int>({ 0, 0, 0, 0, 1, 1, 0, 0 }),
	vector<int>({ 0, 0, 0, 0, 1, 1, 0, 0 }),
	vector<int>({ 1, 0, 0, 0, 1, 1, 1, 1 }),
	vector<int>({ 0, 1, 0, 0, 1, 1, 1, 1 }),
	vector<int>({ 0, 0, 1, 1, 1, 1, 1, 1 }),
	vector<int>({ 0, 0, 1, 1, 1, 1, 1, 1 })
	});

//vector<vector<int> > arr;

int n, gray, white;

void f(int a, int b, int n)
{
	bool isOne = 1;
	for (int i = a; i < a + n; i++)
		for (int j = b; j < b + n; j++)
			if (arr[a][b] != arr[i][j])
				isOne = 0;
	if (isOne)
	{
		if (arr[a][b] == 1) white++;
		else gray++;
		return;
	}
	else
	{
		f(a, b, n / 2);
		f(a + n / 2, b, n / 2);
		f(a, b + n / 2, n / 2);
		f(a + n / 2, b + n / 2, n / 2);
	}
}
int main()
{
	cin >> n;
	
	/*
	vector<int> temp;
	int i, j, k;
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			cin >> k;
			temp.push_back(k);
		}
		arr.push_back(temp);
		temp.clear();
	}
	*/
	
	f(0, 0, n);
	cout << gray << endl; 
	cout << white << endl;

	return 0;
}