BOJ 6603 로또 / BOJ 1759 암호 만들기 / BOJ 2468 안전 영역 (백트래킹, DFS)

백준 BOJ 6603번 : 로또

Solved.ac 난이도 : Silver II

알고리즘 분류 : 백트래킹

 

N개의 로또로 뽑힐 수 있는 후보 번호들이 주어지고, 그들 중 6개의 로또가 뽑힌다고 할 때 나올 수 있는 로또 조합들을 오름차순으로 출력하는 문제입니다.

 

재귀함수를 이용한 백트래킹을 구현하는 대표적인 문제입니다.

다음과 같이 idx, cnt 두 개의 변수를 가지는 재귀함수를 이용하여 DFS를 구현해주면 됩니다.

 

idx는 현재 탐색 중인 인덱스를 의미하고, cnt는 현재까지 뽑은 번호의 개수를 의미합니다.

 

 

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

int N;
vector<int> arr, lotto(6);

void DFS(int idx, int cnt) {
    if(cnt == 6) {
        for(int i=0; i<lotto.size(); i++) cout << lotto[i] << " ";
        cout << "\n";
        return;
    }

    for(int i=idx; i<N; i++) {
        lotto[cnt] = arr[i];
        DFS(i+1, cnt+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(NULL), cout.tie(NULL);

    while(true) {
        cin >> N;
        if(N == 0) break;

        arr.resize(N);
        for(int i=0; i<N; i++) cin >> arr[i];

        DFS(0, 0);
        cout << "\n";
    }
}

 

 

백준 BOJ 1759번 : 암호 만들기

Solved.ac 난이도 : Gold V

알고리즘 분류 : 백트래킹

 

N개의 문자 후보가 주어지고 만들어야 하는 문자열의 길이는 K이며, 문자열은 반드시 사전순 정렬이 되어야하고 최소 1개의 모음과 2개의 자음을 포함한다고 할 때 가능한 모든 문자열을 사전순으로 출력해야하는 문제입니다.

 

의도하고 고른 문제는 아닙니다만, 우연히 위의 문제와 아주 비슷한 백트래킹 문제입니다.

위의 로또 문제와 거의 똑같이 구현해주면 되며, 차이점은 가능한 문자열 후보는 반드시 모음 한 개 이상과 자음 두 개 이상을 포함하고 있다는 조건문이 추가되었다는 것입니다.

조건문은 어디에 추가해도 되겠지만, 가장 간단하게 마지막에 출력하기 전에 검사해서 조건에 부합하지 않을 시 return;으로 종료해주면 쉽습니다.

 

 

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

int K, N;
vector<char> arr, ans;

void DFS(int idx, int cnt) {
    if(cnt == K) {
        int aeiou = 0;
        for(int i=0; i<ans.size(); i++)
            if(ans[i] == 'a' || ans[i] == 'e' || ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u') aeiou++;

        if(aeiou < 1 || ans.size() - aeiou < 2) return;

        for(int i=0; i<ans.size(); i++) cout << ans[i];
        cout << "\n";
        return;
    }

    for(int i=idx; i<N; i++) {
        ans[cnt] = arr[i];
        DFS(i+1, cnt+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> K >> N;

    arr.resize(N);
    ans.resize(K);

    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    DFS(0, 0);
}

 

 

백준 BOJ 2468번 : 안전 영역

Solved.ac 난이도 : Silver II

알고리즘 분류 : DFS

 

N×N 크기의 지도에 대해서 각 블럭의 높이가 주어지고, 특정 높이만큼 비가 왔을 때 잠기지 않는 영역 덩어리의 수를 구한다고 할 때, 다양한 강수량의 높이 중 최대 영역의 수를 구하는 문제입니다.

 

간단한 DFS로 구현하되, 비가 올 수 있는 범위를 0에서부터 최대 블럭의 높이까지 모두 조절해보면서 브루트포스 알고리즘으로 완전 탐색을 해주면 구할 수 있습니다.

(N이 최대 100이고 블럭의 높이도 최대 100이므로 아주 짧은 시간 안에 탐색을 끝낼 수 있습니다.)

 

 

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

int N;
int arr[MAX][MAX];
bool visited[MAX][MAX];

void DFS(int x, int y, int z) {
    visited[x][y] = true;

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

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

        if(arr[nx][ny] > z && !visited[nx][ny]) DFS(nx, ny, z);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;

    int maxh = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            cin >> arr[i][j];
            maxh = max(maxh, arr[i][j]);
        }

    int ans = 0;
    for(int k=0; k<maxh; k++) {
        int cnt = 0;
        memset(visited, false, sizeof(visited));

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                if(arr[i][j] > k && !visited[i][j]) {
                    DFS(i, j, k);
                    cnt++;
                }

        ans = max(ans, cnt);
    }

    cout << ans;
}