[알고리즘 중급] 재귀 - 2

백트래킹

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

백트래킹에 따라 최적화가 달라진다.

 

💚 9663 N-Queen

대표적인 백트래킹 문제이다.

N X N 크기의 체스판 위에 Queen을 N개 놓는 방법의 수를 구하는 문제

브루트포스 시에는 칸에 퀸이 있음 또는 없음 ➡️ 2^N^2

 

하나의 행/열에는 퀸이 하나만 가능하다는 점을 고려하면 체스판의 절반만 확인하면 되므로 N!까지 경우의 수를 줄일 수 있다.

calc(row): row 행에 퀸을 어디에 놓을지 결정해야 함

 

Check 부분을 배열을 이용하면 놓을 수 있는지 검사를 O(1)만에 해결할 수 있다.

 

#include <iostream>
using namespace std;

bool a[14][14];
int n;
bool check_col[14];
bool check_dig[28];
bool check_dig2[28];

bool check(int row, int col) {
    // row는 확인할 필요 없음
    // |
    if(check_col[col]) {
        return false;
    }

    // 오른쪽 위 대각선(/)
    if(check_dig[row + col]) {
        return false;
    }

    // 왼쪽 위 대각선(\)
    // row - col이 음수인 경우를 위해 + n
    if(check_dig2[row - col + n - 1]) {
        return false;
    }

    return true;
}

int calc(int row) {
    if(row == n) {
        return 1;
    }
    int cnt = 0;
    for(int col = 0;col < n;col++) {
        if(check(row, col)) {
            check_dig[row + col] = true;
            check_dig2[row - col + n - 1] = true;
            check_col[col] = true;
            cnt += calc(row + 1);
            // 원상복구
            check_dig[row + col] = false;
            check_dig2[row - col + n - 1] = false;
            check_col[col] = false;
        }
    }

    return cnt;
}

int main() {
    cin >> n;
    cout << calc(0) << '\n';
    return 0;
}

💚 2580 스도쿠

절대로 놓을 수 없는 수는 지나치고 진행을 한다.

백트래킹의 Base는 브루트포스이나, 더 이상 확인해볼 필요가 없는 경우는 호출을 중단하는 것이다.

go(z): z번째 칸을 채우는 함수

(x,y): 9 * x + y번째 칸 

#include <iostream>
using namespace std;

int a[10][10];
// i행에 숫자 j가 있으면 true
bool c[10][10];
// i열에 숫자 j가 있으면 true
bool c2[10][10];
// i번 작은 정사각형에 숫자 j가 있으면 true
bool c3[10][10];

int n = 9;

int square(int x, int y) {
    return (x / 3) * 3 + (y / 3);
}

bool go(int z) {
    if(z == n * n) {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    int x = z / n;
    int y = z % n;

    // 수가 있으면 다음 칸으로 넘어가기
    if(a[x][y]) {
        return go(z + 1);
    }
    else {
        for(int i = 1;i <= n;i++) {
            if(!c[x][i] && !c2[y][i] && !c3[square(x, y)][i]) {
                c[x][i] = c2[y][i] = c3[square(x, y)][i] = true;
                a[x][y] = i;
                if(go(z + 1)) {
                    return true;
                }
                a[x][y] = 0;
                c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;
            }
        }
    }
    return false;
}

int main() {
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
            if(a[i][j] != 0) {
                c[i][a[i][j]] = true;
                c2[j][a[i][j]] = true;
                c3[square(i, j)][a[i][j]] = true;
            }
        }
    }
    go(0);
    return 0;
}

💚 4574 스노미노쿠

위 스도쿠에 도미노가 결합된 문제이다.

여기서는 x,y의 결합을 표현하기 위해 tuple 헤더에 있는 tie(x,y), make_pair을 사용해주었다.

#include <iostream>
#include <cstring>
#include <tuple>
using namespace std;

int a[10][10];
// i행에 숫자 j가 있으면 true
bool c[10][10];
// i열에 숫자 j가 있으면 true
bool c2[10][10];
// i번 작은 정사각형에 숫자 j가 있으면 true
bool c3[10][10];

bool domino[10][10];

// 세로 도미노, 가로 도미노
int dx[] = {0, 1};
int dy[] = {1, 0};

pair<int, int> convert(string s) {
    return make_pair(s[0] - 'A', s[1] - '1');
}


int n = 9;

int square(int x, int y) {
    return (x / 3) * 3 + (y / 3);
}

// a[x][y]에 num이라는 숫자가 들어갈 수 있는가
bool can(int x, int y, int num){
    return !c[x][num] && !c2[y][num] && !c3[square(x, y)][num];
}

void check(int x, int y, int num, int value) {
    c[x][num] = value;
    c2[y][num] = value;
    c3[square(x, y)][num] = value;
}

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool go(int z) {
    if(z == n * n) {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                cout << a[i][j];
            }
            cout << '\n';
        }
        return true;
    }
    int x = z / n;
    int y = z % n;

    // 수가 있으면 다음 칸으로 넘어가기
    if(a[x][y]) {
        return go(z + 1);
    }
    else {
        for(int k = 0;k < 2;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(!inside(nx, ny)) continue;

            // 이미 숫자 존재
            if(a[nx][ny]) continue;

            // 도미노 값 조합 생성
            for(int i = 1;i <= n;i++) {
                for(int j = 1;j <= n;j++) {
                    if(i == j) continue;
                    // 이미 사용한 도미노이면 불가능
                    if(domino[i][j]) continue;
                    if(can(x, y, i) && can(nx, ny, j)) {
                        check(x, y, i, true);
                        check(nx, ny, j, true);
                        domino[i][j] = domino[j][i] = true;
                        a[x][y] = i;
                        a[nx][ny] = j;
                        // 숫자 채우고 그 다음 칸으로 진행
                        if(go(z + 1)) {
                            return true;
                        }
                        check(x, y, i, false);
                        check(nx, ny, j, false);
                        domino[i][j] = domino[j][i] = false;
                        a[x][y] = 0;
                        a[nx][ny] = 0;
                    }
                }
            }

        }
    }
    return false;
}

int main() {
    int tc = 1;

    while(true) {
        memset(c, false, sizeof(c));
        memset(c2, false, sizeof(c2));
        memset(c3, false, sizeof(c3));
        memset(domino, false, sizeof(domino));
        memset(a, false, sizeof(a));
        int m;
        cin >> m;

        if(m == 0) break;
        for(int i = 0;i < m;i++) {
            int n1, n2;
            string s1, s2;

            cin >> n1 >> s1 >> n2 >> s2;
            int x1, y1, x2, y2;
            tie(x1, y1) = convert(s1);
            tie(x2, y2) = convert(s2);
            a[x1][y1] = n1;
            a[x2][y2] = n2;
            domino[n1][n2] = domino[n2][n1] = true;
            check(x1, y1, n1, true);
            check(x2, y2, n2, true);
        }

        for(int i = 1;i <= 9;i++) {
            string s;
            cin >> s;
            int x, y;
            tie(x, y) = convert(s);
            a[x][y] = i;
            check(x, y, i, true);
        }

        cout << "Puzzle " << tc << '\n';
        go(0);
        tc += 1;
    }
    return 0;
}

💚 1987 알파벳

check(board, check, x, y, cnt)

- board: 보드

- check: 방문한 알파벳

- x,y: 현재 위치

- cnt: 방문한 칸의 수

 

새로운 칸 nx, ny로 이동할 수 있는 경우

- go(board, check, nx, ny, cnt + 1)

- 이 때 check는 변경해줘야함

#include <iostream>
#include <vector>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0,};
int n, m;
bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int go(vector<string> &board, vector<bool> &check, int x, int y) {
    int ans = 0;
    for(int k = 0;k < 4;k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if(inside(nx, ny)) {
            if(!check[board[nx][ny] - 'A']) {
                check[board[nx][ny] - 'A'] = true;
                int next = go(board, check, nx, ny);
                if(ans < next) ans = next;
                check[board[nx][ny] - 'A'] = false;
            }
        }
    }
    // 재귀를 통해 얻은 방문 수 + 현재 함수 내에서 방문한 수
    return ans + 1;
}

int main(){
    cin >> n >> m;
    vector<string> board(n);
    for(int i = 0;i < n;i++) {
        cin >> board[i];
    }

    vector<bool> check(26);
    // 좌측 상단에서 시작
    check[board[0][0] - 'A'] = true;
    cout << go(board, check, 0, 0) << '\n';
    return 0;
}

💡추가(중요!!!!!)

💚 14501 퇴사

- N + 1일이 되는 날 퇴사를 하려고 한다(1 <= N <= 15)

- 남은 N일 동안 최대한 많은 상담을 하려고 한다.

- 하루에 하나의 상담을 할 수 있고

- i일에 상담을 하면, T[i]일이 걸리고 P[i]원을 번다.

 

브루트 포스로도 풀 수 있고, 다이나믹 프로그래밍으로도 풀 수 있다.

 

브루트 포스

go(day, sum)

- day 일이 되었다. day 일에 있는 상담을 할지 말지 결정해야 한다.

- 지금까지 얻은 수익은 sum이다.

 

정답을 찾은 경우

- day == n

 

불가능한 경우

- day > n

 

다음 경우

- 상담을 한다: go(day + t[day], sum + p[day])

- 상담을 하지 않는다 : go(day + 1, sum) 

 

주어진 예시를 참고하면 4일이 된 경우에 선택할 수 있는 상담의 방법은 1~3일에 영향을 받지 않는다.

그래서 1~3일에 얻을 수 있는 최대 수익만이 궁금할 뿐이다.

i일부터 상담을 진행했을 때 얻을 수 있는 최대 수익을 저장하면 메모이제이션을 활용할 수 있다.

초기화는 -1로 하고, 방법을 탐색하던 중 -1이 아니면 이미 이전에 탐색했던 방법이라는 뜻이다.

 

dp[i] : i일부터 상담을 진행했을 때 얻을 수 있는 최대 수익

이 방식은 흔히 우리가 첫날부터 DP를 시도하는 방식이 아니다. 오히려 뒤에서부터 DP가 활용된다.

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 100000000;
// 상담 소요 기간
int t[20];
// 상담 수익
int p[20];
// i일부터 상담을 진행했을 때 얻을 수 있는 최대 수익
int d[20];
int n;
int go(int day) {
    // 수익 없음
    if(day == n + 1) {
        return 0;
    }

    // 퇴사 이후 종료되는 일은 담당 불가
    if(day > n + 1) {
        return -INF;
    }

    // 이미 탐색해본 방식으로 최대 수익 방식을 알고 있음
    if(d[day] != -1) {
        return d[day];
    }

    int t1 = go(day + 1);
    int t2 = p[day] + go(day + t[day]);
    d[day] = max(t1, t2);
    return d[day];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;

    for(int i = 1;i <=n;i++) {
        cin >> t[i] >> p[i];
        d[i] = -1;
    }

    cout <<go(1) << '\n';
    return 0;
}

 

 

이전에 작성했던 다른 버전의 DP

dp[i] : i일에 끝낼 수 있는 일까지 고려해서 벌 수 있는 최댓값

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int>> counseling;
// dp[i] : i일에 끝낼 수 있는 일까지 고려해서 벌 수 있는 최댓값
int dp[15];
int main(void){
    int n, t, p;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> t >> p;
        counseling.push_back({t,p});
    }
    // 첫날 소요 기간에 따라 시작값 다름
    if(counseling[0].first == 1){
        dp[0] = counseling[0].second;
    }
    else {
        dp[0] = 0;
    }
    for(int i = 1;i < n;i++){
        // 아무 스케줄도 안 잡는 경우 고려
        dp[i] = dp[i - 1];
        for(int j = 0;j <= i;j++){
            if(j + counseling[j].first - 1 == i){
                dp[i] = max(dp[i], dp[j - 1] + counseling[j].second);
            }
        }
    }
    cout << dp[n - 1];
}

 

참고

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제