이번专题에서는 재귀와 백트래킹 알고리즘에 대해 심도 있게 다루어 보겠습니다. 주로 온라인 저지 사이트에서 수집한 문제들을 바탕으로 설명하며, 필요한 경우 예제 코드를 포함합니다.
- 순열과 조합 =======
1.1 기본 조합 문제(출처: leetcode)
문제: 두 정수 n과 k가 주어졌을 때, 1부터 n까지의 정수 중에서 k개를 선택하는 모든 조합을 반환합니다.
class Solution {
private:
vector<vector<int>> 집합; // 조합 결과 저장
vector<int> 현재경로; // 현재 조합 저장
void 백트래킹(int 최대값, int 선택개수, int 시작인덱스) {
if (현재경로.size() == 선택개수) {
집합.push_back(현재경로);
return;
}
for (int i = 시작인덱스; i <= 최대값; i++) {
현재경로.push_back(i); // 요소 추가
백트래킹(최대값, 선택개수, i + 1); // 재귀 호출
현재경로.pop_back(); // 백트래킹: 요소 제거
}
}
public:
vector<vector<int>> 조합(int n, int k) {
백트래킹(n, k, 1);
return 집합;
}
};
1.2 최적화: 상태 압축 해법(출처: acwing)
1부터 n까지의 정수들 중에서 임의 개수를 선택하여 모든 가능한 조합을 출력하세요(1 <= n <= 15).
재귀 백트래킹과 깊이 우선 탐색은 유사한 점이 많습니다: DFS는 시작점에서 목표까지 앞으로 나아가며 되돌아오지 않는 반면, 두 방법 모두 함수 시작점에 종료 조건을 설정하고 조건이 충족되면 return합니다.
acwing의 아이디어: 선택 상태(선택/미선택)를 비트의 0/1로 압축합니다. n이 15 이하이므로 int 타입으로 상태를 표현할 수 있으며, 0을 1로 변경하는 것은 비트 연산(OR)으로 구현합니다.
#include <bits/stdc++.h>
using namespace std;
int n=0, 상태=0;
void dfs(int 현재위치, int 상태)
{
if (현재위치==n)
{
for(int j=0;j<n;j++)
{
if (상태>>j&1) cout<<j+1<<' ';
}
cout<<endl;
return;
}
dfs(현재위치+1, 상태);
dfs(현재위치+1, 상태 | (1<<현재위치));
}
int main()
{
cin>>n;
dfs(0,0);
return 0;
}
- 체스판 문제 =====
2.1 스도쿠 풀기(출처: leetcode)
스도쿠 풀이 규칙:
- 숫자 1-9는 각 행에 한 번만 나타날 수 있습니다.
- 숫자 1-9는 각 열에 한 번만 나타날 수 있습니다.
- 숫자 1-9는 각 군(3x3)에 한 번만 나타날 수 있습니다.
- 빈 칸은 '.'로 표시됩니다.
아홉 여왕 문제와 유사한 접근 방식: 각 '.' 위치에서 재귀 백트래킹을 사용하며, isValid 함수는 약간 다릅니다.
class Solution {
private:
bool 백트래킹(vector<vector<char>>& 보드) {
for (int i = 0; i < 보드.size(); i++) { // 행 순회
for (int j = 0; j < 보드[0].size(); j++) { // 열 순회
if (보드[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) { // (i, j) 위치에 k를 배치할 수 있는지 확인
if (유효확인(i, j, k, 보드)) {
보드[i][j] = k; // k 배치
if (백트래킹(보드)) return true; // 적합한 조합이 발견되면 즉시 반환
보드[i][j] = '.'; // 백트래킹: k 제거
}
}
return false; // 9개 숫자 모두 시도했지만 실패한 경우
}
}
}
return true; // 모든 위치를 확인했으나 실패하지 않은 경우
}
bool 유효확인(int 행, int 열, char 값, vector<vector<char>>& 보드) {
for (int i = 0; i < 9; i++) // 행 중복 확인
if (보드[행][i] == 값) return false;
for (int j = 0; j < 9; j++) // 열 중복 확인
if (보드[j][열] == 값) return false;
int 시작행 = (행 / 3) * 3;
int 시작열 = (열 / 3) * 3;
for (int i = 시작행; i < 시작행 + 3; i++) { // 3x3 영역 중복 확인
for (int j = 시작열; j < 시작열 + 3; j++)
if (보드[i][j] == 값)
return false;
}
return true;
}
public:
void 스도쿠풀기(vector<vector<char>>& 보드) {
백트래킹(보드);
}
};
2.2 복잡한 스위치(출처: acwing)
25개의 전구가 5×5 정방형으로 배열되어 있습니다. 각 전구에는 스위치가 있으며, 게이머는 상태를 변경할 수 있습니다. 각 단계에서 게이머는 특정 전구의 상태를 변경할 수 있습니다. 게이머가 전구 하나의 상태를 변경하면 연쇄 반응이 발생합니다: 이 전구의 상하좌우에 있는 전구들도 상태가 변경됩니다. 1은 켜진 전구를, 0은 꺼진 전구를 나타냅니다. n개 게임의 초기 상태가 주어졌을 때, 모든 전구를 켜는 데 6단계 이내로 가능한지 확인하는 프로그램을 작성하세요.
비트 연산 기법: 데이터 저장 시 char 타입을 사용하며, char와 int의 XOR 연산 결과는 여전히 char입니다. 예: '1'^1='0'.
핵심 아이디어: 전역 최적 해를 찾기 위해 모든 방안을 체계적으로 검토해야 합니다. 최소 단계 수를 보장하기 위해 2행 이후의 모든 행의 동작은 관찰 가능하므로, 첫 행의 모든 방안을 열거하고 마지막 행으로 전달된 전구들이 모두 켜지는지 확인하기만 하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
const int N=6;
int dx[N]={-1,0,1,0,0},dy[N]={0,1,0,-1,0};
char g[N][N], 백업[N][N];
void 전구변경 (int x, int y)
{
for (int i=0;i<5;i++)
{
int a=x+dx[i], b=y+dy[i];
if (a<0 || a>4 || b<0 || b>4) continue;
g[a][b]^=1;
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=0;i<5;i++) cin>>g[i];
memcpy(백업, g, sizeof g);
int res=10;
for (int op=0;op<32;op++)
{
int 단계=0;
for (int i=0;i<5;i++)
{
if (op>>i&1)
{
단계++;
전구변경(0,i);
}
}
for (int i=0;i<4;i++)
{
for (int j=0;j<5;j++)
{
if (g[i][j]=='0')
{
단계++;
전구변경(i+1,j);
}
}
}
bool 완료=true;
for (int i=0;i<5;i++)
{
for (int j=0;j<5;j++)
{
if (g[i][j]=='0')
{
완료=false;
break;
}
}
}
if (완료) res=min(res, 단계);
memcpy(g, 백업, sizeof g);
}
if (res>6) res=-1;
cout<<res<<endl;
}
return 0;
}
2.3 동전 뒤집기(출처: acwing)
초기 상태와 목표 상태가 주어졌을 때, 인접한 두 동전만 동시에 뒤집을 수 있다면 특정 상태를 만들기 위해 최소 몇 번의 뒤집기가 필요할까요?
핵심 아이디어: 최적 해 과정 추론
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str1,str2;
cin>>str1>>str2;
int cnt=0;
int str1_len=str1.size();
for (int i=0;i<str1_len-1;i++)
{
if (str1[i]!=str2[i])
{
cnt++;
if (str1[i]=='*') str1[i]='o';
else str1[i]='*';
if (str1[i+1]=='*') str1[i+1]='o';
else str1[i+1]='*';
}
}
cout<<cnt;
return 0;
}
- 구성원 분할 ======
3.1 분수 문제(출처: acwing)
주어진 양의 정수에 대해, 1~9의 숫자를 중복 없이 모두 사용하여 분수 형식으로 표현할 수 있는 모든 경우의 수를 출력하세요.
매우 창의적인 접근법:
19의 숫자가 각각 한 번만 사용되어야 하므로, 19의 모든 순열을 생성하고 다양한 방식으로 순열을 나누어 세 숫자를 얻은 다음 조건을 만족하는지 확인할 수 있습니다.
핵심 아이디어:
- 나눌 때 i, j for 루프를 사용하며 항상 j > i를 유지합니다.
- next_permutation(nums, nums+9)은 9개 요소 배열에서 다양한 순열을 생성합니다.
#include <bits/stdc++.h>
using namespace std;
int n;
int nums[9]={1,2,3,4,5,6,7,8,9};
int 계산(int 시작, int 끝)
{
int res=0;
for (int i=시작;i<=끝;i++) res=res*10+nums[i];
return res;
}
int main()
{
cin>>n;
int res=0;
do{
for (int i=0;i<9;i++)
{
for (int j=i+1;j<9;j++)
{
int a=계산(0,i);
int b=계산(i+1,j);
int c=계산(j+1,8);
if (a==0 || b==0 || c==0) continue;
if (a*c +b ==c*n) res++;// 곱셈으로 변환하여 정밀도 향상
}
}
}while(next_permutation(nums, nums+9));
cout<<res<<'\n';
return 0;
}
- 미로 탐색 ======
4.1 문자 미로(출처: OJ4C)
2D 문자 행렬과 소문자로만 구성된 문자열이 주어졌을 때, 문자 행렬에서 주어진 문자열의 부분 문자열과 일치하는 경로를 찾을 수 있는지 확인하고, 가장 긴 일치하는 부분 문자열을 출력하세요.
- 문자 행렬에서 인접한 가장자리 또는 모서리는 모두 유효한 경로입니다.
- 일치 과정은 문자의 대소문자를 구분하지 않으며, 물음표(?)는 임의의 단일 문자와 일치하는 와일드카드로 사용될 수 있습니다.
- 별표(*) 문자는 동일한 문자를 여러 번 일치시킬 수 있습니다.
- 별표가 있는 위치를 제외한 다른 문자 위치는 경로에서 중복 사용할 수 없습니다.
접근법: 복잡한 규칙 판정, 미세한 오류가 발생하기 쉬움 각 위치에서 8방향으로 검색하며, altc 표를 유지합니다(유사한 2D 데이터를 여러 표로 저장하여 동일한 인덱스로 접근함)
#include <bits/stdc++.h>
using namespace std;
#define MAX 501
int 방향[8][2]={{-1,1},{-1,0},{-1,-1},{0,1},{0,-1},{1,1},{1,0},{1,-1}};
char 미로[MAX][MAX]={{'\0'}};
char altc[MAX][MAX]={{'\0'}};
int 상태[MAX][MAX]={{0}};
string 문자열="";
int 문자열길이=0, 최대길이=0;
bool 일치확인(int 위치, int 행, int 열)
{
if (위치<0 || 위치>=문자열길이)
return false;
if (문자열[위치]==미로[행][열] || 미로[행][열]=='?')
return true;
if ((미로[행][열]=='*'&&altc[행][열]=='\0') || 문자열[위치]==altc[행][열])
return true;
return false;
}
void 동일문자이동(int &길이, int &위치)
{
char 참조=문자열[위치];
for (int i=위치+1;i<문자열길이;i++)
{
if (문자열[i]!=참조)
break;
길이++, 위치++;
}
}
void 탐색(int 위치, int 길이, int 행, int 열)
{
if (!일치확인(위치, 행, 열) || 길이==문자열길이)
{
if (길이>최대길이)
최대길이=길이;
return;
}
길이++;
if (미로[행][열]=='*')
동일문자이동(길이, 위치);
for (int i=0;i<8;i++)
{
int r=행+방향[i][0];
int c=열+방향[i][1];
if (미로[r][c]=='*')
{
bool f=(altc[r][c]=='\0');
if (f)
altc[r][c]=문자열[위치+1];
탐색(위치+1, 길이, r, c);
if (f)
altc[r][c]='\0';
}
else
{
if (상태[r][c])
continue;
상태[r][c]=1;
탐색(위치+1, 길이, r, c);
상태[r][c]=0;
}
}
}
int main ()
{
int m,n;
cin>>m>>n;
for (int i=1;i<=m;i++)
{
scanf("%s", &미로[i][1]);
strlwr(&미로[i][1]);
상태[i][0]=상태[i][n+1]=1;
}
for (int i=0;i<=n+1;i++)
{
상태[0][i]=상태[m+1][i]=1;
}
cin>>문자열;
문자열길이=문자열.size();
int 시작위치=0, 길이=0;
for (int i=0;i<문자열길이;i++)
{
for (int r=1;r<=m;r++)
{
for (int c=1;c<=n;c++)
{
최대길이=0;
if (미로[r][c]=='*')
{
altc[r][c]=문자열[i];
탐색(i, 0, r, c);
altc[r][c]='\0';
}
else if (미로[r][c]=='?' || 미로[r][c]==문자열[i])
{
상태[r][c]=1;
탐색(i, 0, r, c);
상태[r][c]=0;
}
if (최대길이>길이)
{
길이=최대길이;
시작위치=i;
}
}
}
}
for (int i=시작위치;i<시작위치+길이;i++)
cout<<문자열[i];
return 0;
}
4.2 게임 전략(출처: OJ4C)
학기 말이 다가오면서 스트레스가 증가한 이레이와 한메이 메이 학생들은 간단한 탐험 게임으로 긴장한 학습 리듬을 조절합니다. 게임 인터페이스는 생동감 있지만, 게임 캐릭터를 제어하는 기본 지도와 게임 미션은 단지 격자 행렬일 뿐입니다. 각 격자에는 두 개의 양의 정수가 할당되어 있으며, 이는 해당 위치의 게임 미션 난이도 D와 주변 인접 격자와의 연결성 L을 제어합니다. 미션 난이도는 예상 평균 완료 시간(분)으로 측정되며, 연결 조건은 L[r1, c1] ≤ L[r2, c2]로 표시되며, 이는 격자 [r1, c1]에서 주변(8개) 인접 격자 중 [r2, c2]로 이동할 수 있음을 의미합니다.
게임의 고정 규칙은 되돌아가는 길이 없지만, 게이머는 이미 방문한 위치에 들어가지 않도록 해야 합니다. 그렇지 않으면 시간 낭비뿐만 아니라 끝없는 상태에 빠질 수 있습니다. 게임 시작 시, 게이머가 동일한 방향으로 K개 이상의 격자를 연속으로 이동하지 못하도록 제한을 설정할 수도 있습니다. 이는 게임의 재미를 더하기 위함입니다.
게임 입구는 행렬의 왼쪽 아래 모서리이고, 출구는 오른쪽 위 모서리입니다. 이레이와 한메이 메이 학생들이 게임 시작 후 모든 미션을 완료하는 데 필요한 최소 시간을 예측하는 프로그램을 작성하세요.
문자 미로 문제와 유사한 접근 방식이지만, 조건이 더 적으며 전체 그래프에 대한 너비 우선 탐색을 통해 해결합니다.
#include <bits/stdc++.h>
using namespace std;
#define MAX 25
int 방향[8][2]={{-1,1},{-1,0},{-1,-1},{0,1},{0,-1},{1,1},{1,0},{1,-1}};
int L[MAX][MAX];
int 상태[MAX][MAX];
int T[MAX][MAX];
int 최소시간=INT_MAX;
int n,k;
void 해결(int 행, int 열, int 시간, int 단계, int 방향)
{
시간+=T[행][열];
if (행==1 && 열==n)
{
if (시간<최소시간) 최소시간=시간;
return;
}
if (행<1 || 행>n || 열<1 || 열>n) return;
for (int i=0;i<8;i++)
{
int r=행+방향[i][0];
int c=열+방향[i][1];
if (L[r][c]<L[행][열]) continue;
if (시간+T[r][c]>최소시간) continue;
if (상태[r][c]) continue;
if (방향==i) 단계++;
else 단계=1;
if (k && 단계==k+1) continue;
상태[r][c]=1;
해결(r, c, 시간, 단계, i);
상태[r][c]=0;
}
}
int main ()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
cin>>L[i][j];
상태[i][0]=상태[i][n+1]=1;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>T[i][j];
for (int i=0;i<=n+1;i++)
상태[0][i]=상태[n+1][i]=1;
상태[n][1]=1;
해결(n,1,0,0,0);
cout<<최소시간;
return 0;
}