강의
https://www.youtube.com/watch?v=Enz2csssTCs&t=3s
설명
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
dfs와의 차이점: dfs는 모두 탐색. backtracking은 막히면 더 깊이 들어가지 않고 이전 단계로 돌아감 비슷한데 다름
next_permutation
헤더: <algorithm>
template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);순열을 만들어주는 함수.
https://twpower.github.io/82-next_permutation-and-prev_permutation
next_permutation로 조합 구하기
전체 n개의 원소들 중에서 k개를 뽑는 조합(=nCk)을 구한다면 n개의 벡터 원소에 1을 k개 0을 나머지인 n-k개 집어넣어서 순열을 돌리고 1에 해당하는 인덱스만 가져오면 된다.
이 때 0 0 .. 1 1 .. 이런식의 꼴로 시작해야함!! next_permutation 순서가 0 0 .. 1 1 .. 로 시작해서 1 1 .. 0 0 .. 으로 끝남
https://twpower.github.io/82-next_permutation-and-prev_permutation
이유: next_permutation은 중복이 있는 원소의 경우 중복인 경우를 제외하고 순열을 만들어 준다.
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0 대충 흐름을 보면 n개의 원소중 1에 해당하는 인덱스가 조합에 포함된다고 보면 되는 것을 알 수 있음
문제
https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0C.md
visited를 어떻게 활용해야 할지를 잘 생각해보면 된다
15649
재귀 함수 들어가기 전에 내 노드를 visited 표시하고, 재귀함수를 나오면 내 노드가 visited인 상태에서 탐색이 다 끝난 거니까 다시 visited를 false로 바꿔줌
9663
n퀸 문제. 백트래킹이라 15649랑 비슷하게 풀면 됨. 대신 이번에 visited를 내 열에 해당하는 것, 내 왼쪽 대각선에 해당하는 것, 오른쪽 대각선에 해당하는 것 세 개를 써야 함.
1182
재귀를 타고가는 아이디어: arr[i]번 째를 포함하는 부분집합으로 갈 건가, 포함하지 않는 부분집합으로 갈 건가.
void f(int k, int total) {
if (k == N) return;
if (total + arr[k] == S) ++ans;
f(k + 1, total);
f(k + 1, total + arr[k]);
}15650
중복인 경우를 제외하고 수열을 만들어줘야 함.
함수 인자에 시작 인덱스를 넘겨주면 됨.
그럼 이번에 나간 인덱스 다음에 있는 원소들로 수열을 만들어주기 때문.
void p(int idx, int k) {
if (k == M) {
for (int i = 0; i < k; ++i) cout << arr[i] << ' ';
cout << '\n';
return;
}
for (int i = idx; i < N; ++i) {
if (vis[i]) continue;
arr[k] = i + 1;
vis[i] = 1;
p(i + 1, k + 1);
vis[i] = 0;
}
}방법2. next_permutation 사용.
int main(void) {
cin >> N >> M;
for (int i = M; i < N; ++i) arr[i] = 1;
do {
for (int i = 0; i < N; ++i) {
if (!arr[i]) cout << i + 1 << ' ';
}
cout << '\n';
} while(next_permutation(arr, arr + N));
}15651
이번엔 같은 수를 여러 번 골라도 되기 때문에 vis배열이 필요가 없음
15652
비내림차순을 만족해야 하기 때문에
if (k > 0 && arr[k - 1] > i + 1) continue;조건을 추가해줌
15654
sort 함수 사용하기. arr[k] = i + 1 대신 ans[k] = arr[i];
15655
시작 인덱스를 함수 인자로 넘겨주면 됨
15656
15651과 똑같음
15666
처음 배열 받을 때 중복 없이 받아줬음 그리고 비내림차순이니까 시작 위치 함수 인자로 넘겨주면 됨
6603
간단한 문제 시작 인덱스 넘겨주면 됨
1759
조건 잘 살피기! aeiou가 하나 이상 있어야 하고 자음이 2개 이상 있어야 함
#include <iostream>
#include <algorithm>
using namespace std;
int L, C, cnt;
char arr[26], ans[26];
bool is_vowel(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
void dfs(int k, int st) {
if (k == L) {
if (cnt < 1) return; // 모음이 하나도 없는 경우였다면 그냥 리턴
for (int i = 0; i < k; ++i) cout << ans[i];
cout << '\n';
return;
}
for (int i = st; i < C; ++i) {
if (is_vowel(arr[i])) {
if (L - (cnt + 1) < 2) continue; // 이번에 모음을 추가했을 때 자음이 2개 미만이 되는 거면 그냥 contiue
++cnt; // 그게 아니라면 모음이 추가될 것이므로 ++cnt
}
ans[k] = arr[i];
dfs(k + 1, i + 1);
if (is_vowel(arr[i])) --cnt; // 모음이 추가됐을 때 상황을 다 돌고 나온 것이기 때문에 다시 --cnt
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> L >> C;
for (int i = 0; i < C; ++i) cin >> arr[i];
sort(arr, arr + C);
dfs(0, 0);
}1941
와.......... 걍 진작 답 볼걸
이건 dfs랑 bfs를 같이 써야 하는 문제.
그새 또 bfs 하는 법 까먹어서 헤맸다;; 역시 복습만이 살 길..
전체 개요
1. dfs로 25C7을 구한다. 25자리 중 7자리를 뽑는 것.
2. 뽑은 자리에 S파가 4명 이상이고
3. bfs로 구한 너비가 7이면 ++ans
dfs를 할 때 뽑힌 자리를 체크해준다. bfs를 하기 위해서!!
조합으로 뽑힌 자리만 1로 채워준 combi7[5][5] 배열을 만들어준다.
그래야 bfs를 할 때 1인 부분만(조합으로 뽑힌 자리만) 탐색해 나갈 수 있으니까
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define X first
#define Y second
char board[5][5];
int arr[7], combi7[5][5], ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int bfs(int r, int c) {
queue<pair<int, int> > q;
bool vis[5][5] = {};
int cnt = 0;
q.push(pair(r, c));
vis[r][c] = 1;
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
++cnt;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
if (vis[nx][ny] || !combi7[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
return cnt;
}
void dfs(int k, int st, int dasom) {
if (k == 7) {
if (dasom >= 4 && bfs(arr[0] / 5, arr[0] % 5) == 7) ++ans;
return;
}
for (int i = st; i < 25; ++i) {
arr[k] = i;
combi7[i / 5][i % 5] = 1; // bfs를 하기 위해 뽑힌 자리를 체크해준다.
dfs(k + 1, i + 1, dasom + (board[i / 5][i % 5] == 'S'));
combi7[i / 5][i % 5] = 0; // dfs를 돌고 나온 후니까 다시 0으로 바꿔줌.
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) cin >> board[i][j];
}
dfs(0, 0, 0);
cout << ans;
}