3주차: 완전 탐색, 백트래킹, 1189번(컴백홈), 17825번(주사위윷놀이), 17136번(색종이붙이기)

완전 탐색

모든 경우의 수를 탐색하는 방법

탐색한 후 초기화 하는 과정!

 

dfs : 쭉 내려가다가 다시 올라간다. (실행은 역순으로) 

Ex) f(1) > f(2) > f(3) 실행될 때는 : f(3) > f(2) > f(1)

 

지난 시간에 풀었던 연구소 문제를 확인해보자.

14502: 연구소

 

벽을 3개 세운다면 어떻게 세울지보다는 벽을 세울 수 있는 공간 중 3개를 뽑아(조합)탐색한다.

그 후 다시 초기화(벽 안세운 상태인 0으로)

 

1436번: 영화감독 숌

666이 포함된 숫자 찾기(작은수부터)

어떻게 찾을지보다 1부터 1++씩 해가며 666이 포함된 숫자 찾기

 

 

1189번: 컴백홈 

다국어

시간 제한            메모리 제한                       제출                      정답                        맞힌 사람                 정답 비율

 

2 초

128 MB

3118

1723

1406

54.900%

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

예제 입력 1 복사

3 4 6
....
.T..
....

예제 출력 1 복사

4

 

흐름

 

코드

#include <bits/stdc++.h>
using namespace std;

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

int r,c,k,visited[10][10]; //거리 표시
char a[10][10];
string s;

int dfs(int y, int x){
    if(y==0 && x==c-1){ //도착시에 가지수 리턴
        if(k==visited[y][x]) return 1;
        return 0;
    }
    int ret=0; //거리 k인 가짓수 구하는 변수
    for(int i=0;i<4;i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0||nx<0||ny>=r||nx>=c||a[ny][nx]=='T'||visited[ny][nx]) continue;
        visited[ny][nx]=visited[y][x]+1; //거리 1씩 더하기
        ret += dfs(ny,nx); //dfs 수행하면서 도착점까지 갔다가 다시 올라오면서 가짓수 회수
        visited[ny][nx]=0; //방문 초기화
    }
    return ret; //가짓수 리턴
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> r >> c >> k;
    for(int i=0;i<r;i++){
        cin >> s;
        for(int j=0;j<c;j++){
            a[i][j]=s[j];
        }
    }
    //2. dfs 수행
    visited[r-1][0]=1; //현재 위치 방문 표시
    cout << dfs(r-1,0) << "\n"; // 현재 위치에서 dfs 수행
}

 

코드 설명

• 도착하는 가짓수를 구하는 문제 = dfs를 이용한 완전탐색
  • 도착시에 종료조건 실행
  • int ret=0; //노드마다 자신의 ret값 가짐
  • ret += dfs(ny,nx) : 리턴값 더해주기
  • visited[ny][nx]=0 : 방문배열 원소 초기화
• 도착시 이동거리 구하기 -> 완전탐색시에는 visited배열에 거리값 넣어주기(dfs처럼)
• visited 배열 : 방문 표시 + 거리표시
• ret: 거리 k인 총 경우의 수 계산
• 이 문제는 dfs로 풀 수 있지만 bfs로는 풀 수 없다. 같은 레벨에 있는 원소를 2번 이상 거쳐갈 경우(한바퀴 돌아 도착하는 경우)가 있기 때문이다.

 

완전탐색이 드러난 코드

int dfs(int y, int x){
    if(y==0 && x==c-1){ //도착시에 가지수 리턴
        if(k==visited[y][x]) return 1;
        return 0;
    }
    int ret=0; //거리 k인 가짓수 구하는 변수
    for(int i=0;i<4;i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0||nx<0||ny>=r||nx>=c||a[ny][nx]=='T'||visited[ny][nx]) continue;
        visited[ny][nx]=visited[y][x]+1; //거리 1씩 더하기
        ret += dfs(ny,nx); //dfs 수행하면서 도착점까지 갔다가 다시 올라오면서 가짓수 회수
        visited[ny][nx]=0; //방문 초기화
    }
    return ret; //가짓수 리턴
}

거리 더한 후 -> 재귀호출 ->  초기화

 

17825번: 주사위 윷놀이

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

512 MB

11584

4858

3032

39.128%

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

 

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1 복사

1 2 3 4 1 2 3 4 1 2

예제 출력 1 복사

190

예제 입력 2 복사

1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

133

예제 입력 3 복사

5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

214

예제 입력 4 복사

5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

130

 

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

17825번: 주사위 윷놀이

 

참고사진

 

선생님 풀이

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[54]; //맵 화살표(방향)
int v[104], a[10], mal[4]; //v:지도, a:주사위, mal: 4개의 말 위치

//주사위 굴리기(현재위치, 주사위):Bfs
int move(int here, int cnt){ 
    if(here==100) return 100; //도착시 리턴값 100
    if(adj[here].size() >= 2){ //출발지가 갈림길이면
        here=adj[here][1]; //두번째길(초록길)
        cnt--;
    } 
    if(cnt){ //주사위 수 존재할때(이동중이면)-bfs
        queue<int> q;
        q.push(here);
        int there;
        while(q.size()){
            int x = q.front(); q.pop();
            there = adj[x][0]; //이동중이면 빨간길로 감
            q.push(there);
            if(there==100) break; //도착하면 stop
            cnt--;
            if(cnt==0) break; //주사위 끝남 
        }
        return there;
    } else return here;
}

//간 곳에 말이 있는지 확인
bool isMal(int mal_idx, int idx){
    if(mal_idx==100) return false; //도착지점에는 몇개의 말이 있어도 상관없음
    //4개의 말 중 하나라도 존재하는지 확인
    for(int i=0;i<4;i++){
        if(i==idx) continue; //자기자신은 확인 X
        if(mal[i]==mal_idx) return true; //말이 존재하면 true
    }
    return false;
}

int go(int here){
    if (here==10) return 0; //주사위 턴 끝남
    int ret = 0;
    //4개의 말
    for(int i=0;i<4;i++){
        int temp_idx = mal[i]; //이전위치
        int mal_idx = move(temp_idx, a[here]); //이전위치, 주사위 => 이동한 위치 리턴
        if(isMal(mal_idx,i)) continue; //이동한 곳에 말이 존재하면 못감
        mal[i] = mal_idx; //말 위치 업데이트
        ret = max(ret, go(here+1)+v[mal_idx]); //다음 위치로 이동, 점수 추가
        mal[i]=temp_idx; //이전위치로 다시 초기화
    }
    return ret; //점수 반환
}

//화살표 표현(here:시작점 -> there:끝점)
void add(int here, int there){
    adj[here].push_back(there);
}
//지도 만들기
void setMap(){
    for(int i=0;i<=19;i++) add(i,i+1); //0~20 인덱스까지 연결
    add(5,21); add(21,22); add(22,23); add(23,24); add(24,25); add(25,26); add(26,20);
    add(10,27); add(27,28); add(28,24); add(15,29); add(29,30); add(30,31); add(31,24);
    add(20,100); //도착지 100

    v[1]=2; v[2]=4; v[3]=6; v[4]=8; v[5]=10; v[6]=12; v[7]=14; v[8]=16; v[9]=18; v[10]=20;
    v[11]=22; v[12]=24; v[13]=26; v[14]=28; v[15]=30;
    v[16]=32; v[17]=34; v[18]=36; v[19]=38; v[20]=40;
    v[21]=13; v[22]=16; v[23]=19; v[24]=25; v[25]=30; v[26]=35; v[27]=22;v[28]=24;
    v[29]=28; v[30]=27; v[31]=26;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    setMap(); //맵 만들기
    for(int i=0;i<10;i++) cin >> a[i]; //주사위 입력받기
    cout << go(0) << "\n"; //출발(주사위 0번째부터 시작)
    return 0;
}

 

완전탐색의 특징이 드러난 코드

 

말 위치 업데이트 후 go함수 실행 => 다시 초기화

 

이해가 잘되도록 다시 작성했다(변수명 등등 조금 바뀜)

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[54]; //지도 화살표
int m[104], d[10], mal[4]; //m:지도. d:주사위, mal: 말 위치

//주사위만큼 말 이동하기
int move(int here, int cnt){
    if(here==100) return 100; //도착칸에 도착
    if(adj[here].size()>=2){ //갈림길이면
        here = adj[here][1]; //두번째 길로
        cnt--;
    }
    //주사위만큼 이동
    if(cnt){
        queue<int> q;
        q.push(here);
        int there;
        while(q.size()){
            int x = q.front(); q.pop();
            there= adj[x][0];
            q.push(there);
            if(there==100) break; //도착지이면 그만 이동
            cnt--;
            if(cnt==0) break; //주사위만큼 감
        }
        return there; //도착지 반환
    }
    else return here; 
}
//도착 위치에 다른 말 존재하는지 확인
bool isMal(int here, int index){
    if(here==100) return false; //도착칸에는 여러개 말 도착 가능 
    for(int i=0;i<4;i++){
        if(i==index) continue; //같은 말이면 검사 X
        if(mal[i]==here) return true;
    }
    return false;
}
// 10개의 주사위를 4개의 말에 ret값이 최대로 되도록 완전탐색(모든 경우 구하기)
int go(int seq){
    if(seq==10) return 0; //주사위 끝
    int ret = 0; //점수값
    for(int i=0;i<4;i++){ //4개의 말 중 하나에 할당
        int temp = mal[i]; //말의 위치
        int update = move(temp, d[seq]); //말이 간 위치(현재위치, 주사위)
        if (isMal(update, i)) continue; //도착한 곳에 말 존재하면 못감(도착위치, 말)
        mal[i]=update; //말 위치 업데이트
        ret = max(ret, go(seq+1) + m[update]); //현재 위치값 점수에 포함, 재귀호출
        mal[i]=temp; //초기화
    }
    return ret;
}

//지도 방향 표현
void add(int a, int b){
    adj[a].push_back(b);
}
//지도 만들기
void setMap(){
    for(int i=0;i<=20;i++) m[i]=2*i;
    m[21]=13; m[22]=16; m[23]=19; m[24]=25; m[25]=30; m[26]=35; m[27]=22; m[28]=24; 
    m[29]=28; m[30]=27; m[31]=26;
    //화살표
    for(int i=0;i<=19;i++) add(i,i+1);
    add(20, 100);
    add(5,21); add(21,22); add(22,23); add(23,24);
    add(10,27); add(27,28); add(28,24);
    add(15,29); add(29,30); add(30,31); add(31,24);
    add(24,25); add(25,26); add(26,20);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    setMap(); //지도 만들기
    for(int i=0;i<10;i++){
        cin >> d[i]; //주사위
    }
    //정답 출력하기(주사위 0번째부터 시작)
    cout << go(0) << "\n";
    return 0;
}

 

백트래킹

완전탐색+가지치기

가지 말아야하는 경우의 수를 파악해서 가지 않는것

 

17825번: 색종이 붙이기

시간 제한           메모리 제한                   제출                              정답                        맞힌 사람                정답 비율

1 초

512 MB

20834

7951

4333

34.452%

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

 

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

예제 입력 1 복사

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

0

예제 입력 2 복사

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

예제 출력 2 복사

4

예제 입력 3 복사

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

예제 출력 3 복사

5

예제 입력 4 복사

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

예제 출력 4 복사

-1

예제 입력 5 복사

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

예제 출력 5 복사

7

예제 입력 6 복사

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 6 복사

4

예제 입력 7 복사

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

예제 출력 7 복사

6

예제 입력 8 복사

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

예제 출력 8 복사

5

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

17136번: 색종이 붙이기

 

흐름

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321; //9억
int a[14][14], ret=INF;
map<int,int> mp;

bool check(int y, int x, int cnt){
    if(y+cnt>10|| x+cnt>10) return false; //종이를 넘어가는 경우
    //종이 붙일 공간에 0 있는지 확인
    for(int i=y;i<y+cnt;i++){
        for(int j=x;j<x+cnt;j++){
            if(a[i][j]==0) return false;
        }
    }
    return true;
}

void draw(int y, int x, int cnt, int value){ //cnt:_size, value:그림(0), 안그림(1)
    for(int i=y;i<y+cnt;i++){
        for(int j=x;j<x+cnt;j++){
            a[i][j]=value; //크기만큼 value 표시
        }
    }
}
void dfs(int y, int x, int cnt){
    if(cnt>=ret) return; //종이 개수가 지금까지 종이개수 최소값보다 크면 가지치기(수행안하고 다음껄로 넘어감)
    //버퍼 오버플로우 체크
    if(x==10){ //다음줄로 넘어감
        dfs(y+1,0,cnt); return;
    }
    if(y==10){ //탐색이 끝날경우 최소값 구함
        ret = min(cnt, ret); return;  //종이 최소 개수 업데이트
    }
    if(a[y][x] == 0){ //0이면 넘어감(오버플로우는 앞에서 체크함)
        dfs(y,x+1,cnt); return;
    }
    for(int _size=5;_size>=1;_size--){ //5*5 ~ 1*1
        if(mp[_size]==5) continue; //5장 초과하면 넘어감
        if(check(y,x,_size)){ //종이 붙일수 있으면
            mp[_size]++; //종이 개수 추가
            draw(y,x,_size, 0); //종이 붙였으니 0으로
            dfs(y,x+_size, cnt+1); //그 다음꺼 호출
            draw(y,x,_size,1); //다시 초기화(종이 붙일 수 있는 상태로)
            mp[_size]--; //종이 개수 감소(초기화)
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cin>>a[i][j];
        }
    }
    //2. dfs 수행
    dfs(0,0,0);
    //종이 개수 출력
    cout << (ret==INF ? -1 : ret) << "\n";
    return 0;
}

 

완전 탐색이 드러난 코드

for(int _size=5;_size>=1;_size--){ //5*5 ~ 1*1
        if(mp[_size]==5) continue; //5장 초과하면 넘어감
        if(check(y,x,_size)){ //종이 붙일수 있으면
            mp[_size]++; //종이 개수 추가
            draw(y,x,_size, 0); //종이 붙였으니 0으로
            dfs(y,x+_size, cnt+1); //그 다음꺼 호출
            draw(y,x,_size,1); //다시 초기화(종이 붙일수 있는 상태로)
            mp[_size]--; //종이 개수 감소(초기화)
        }
    }
    
... 
if (y==10){ //탐색이 끝날경우 최소값 구함
    ret = min(cnt, ret); return;  //종이 최소 개수 업데이트
}

종이 붙이고 다음꺼 수행 후 다시 종이 붙일수있는 초기 상태 만들기

값 업데이트

 

 백트래킹이 드러난 코드

if(y==10){ //탐색이 끝날경우 최소값 구함
        ret = min(cnt, ret); return;  //종이 최소 개수 업데이트
}
...
if(cnt>=ret) return; //종이 개수가 지금까지 종이개수 최소값보다 크면 가지치기(수행안하고 다음껄로 넘어감)

정답이 아닌 케이스는 계속 수행하지않고 종료(return)

 

내가 좀 더 이해하기 쉽게 코드를 다시 작성했다.(거의 같지만 😂)

코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int a[12][12], ret=INF;
map<int,int> mp;

//값 현재위치에서 +size만큼 draw
void draw(int y, int x, int size, int value){
    for(int i=y;i<y+size;i++){
        for(int j=x;j<x+size;j++){
            a[i][j]=value;
        }
    }
}
//종이 붙일 칸이 모두 1인지 확인
bool check(int y, int x, int size){
    for(int i=y;i<y+size;i++){
        for(int j=x;j<x+size;j++){
            if(a[i][j]==0) return false;
        }
    }
    return true;
}
void dfs(int y,int x, int cnt){
    if(cnt >=ret) return; //가지치기
    //오버플로우 확인 (x<10,y<10)
    if(x==10){ //다음줄로 넘어감
        dfs(y+1,0,cnt); return;
    }
    if(y==10){ //끝남, ret값 업데이트
        ret = min(cnt, ret); return;
    }
    if(a[y][x]==0){ //옆으로 넘어감
        dfs(y,x+1,cnt); return;
    }
    //색종이 5*5 ~ 1*1
    for(int size=5;size>=1;size--){
        if(mp[size]==5) continue; //이미 5장 넘으면 다음껄로 넘어가기
        if(check(y,x,size)){ //색종이 붙이기 가능하면
            //색종이 붙이기
            mp[size]++;
            draw(y,x,size,0);
            //다음꺼 호출
            dfs(y,x+size,cnt+1);
            //다시 초기화
            draw(y,x,size,1);
            mp[size]--;
        }
    }
}
int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    //1. 입력받기
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cin >> a[i][j];
        }
    }
    //2. Dfs 수행
    dfs(0,0,0); //(0,0), 색종이 0개
    //3. 정답 출력
    cout << (ret==INF? -1 : ret);
}

 

어렵지만 알고리즘을 잘 짜고 수행 -> 재귀호출 -> 초기화 과정을 지키면 컴퓨터가 정답을 알려줄것이다..

 

 

재귀함수를 이용한 완전탐색

문제

n개의 요석에 꽂을 숫자를 고른다. 숫자들의 합은 소수여야한다.

합이 소수가 되기 위해서는 더하는 수들은 모두 소수여야한다.

모든 경우를 구하기 위해 완전탐색을 이용한다.

--> 수를 선택하거나 선택하지않거나 2가지 경우를 고려한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

const int V=100;
int n, a[V], sum, temp;
vector<int> v;

bool check(int n){ //소수일때 true
	if(n <= 1) return false;
	for(int i = 2; i*i<=n; i++){
		if(n%i==0) return false;
	}
	return true;
}

int go(int idx, int sum){
	if(idx==n) return check(sum); //n개의 합이 소수인지 판단
	return go(idx+1, sum+v[idx]) + go(idx+1, sum); //완전탐색(모든 경우 탐색)
}

int main(){
	//1. 입력받기
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> temp;
		v.push_back(temp);
	} 
	//2. 소수인지 확인
	cout << go(0, 0) << "\n";
	return 0;
}

 

 

백트래킹 : 완전탐색에서 경우의 수를 가지치기로 줄인 것

문제

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, a[V], sum, temp, ret;
vector<int> v;

void go(int idx, int sum){
	if(ret==10) return; //가지치기(mod 11에서 최댓값 10)
	if(idx==n){
		int r = sum%11;
		ret = max(r, ret);
	}
	go(idx+1, sum+v[idx]);
	go(idx+1, sum); //완전탐색(모든 경우 탐색)
}

int main(){
	//1. 입력받기
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> temp;
		v.push_back(temp);
	} 
	//2. 완전탐색
	go(0, 0);
	//3. 정답 출력
	cout << ret << "\n";
	return 0;
}