0x0C강 - 백트래킹
알고리즘 설명
백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
연습 문제 1 - N과 M
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
bool IsUsed[10];
void func(int num)
{
if (num == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++)
{
if (!IsUsed[i])
{
arr[num] = i;
IsUsed[i] = 1;
func(num + 1);
IsUsed[i] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}연습문제 2 n-퀸
#include <bits/stdc++.h>
using namespace std;
int n,cnt;
bool IsUsed1[15];
bool IsUsed2[30];
bool IsUsed3[30];
void func(int num)
{
if (num == n)
{
cnt++;
return;
}
for (int i = 0; i < n; i++)
{
if (IsUsed1[i] || IsUsed2[i + num] || IsUsed3[num - i + n - 1])
continue;
IsUsed1[i] = 1;
IsUsed2[i + num] = 1;
IsUsed3[num - i + n - 1] = 1;
func(num + 1);
IsUsed1[i] = 0;
IsUsed2[i + num] = 0;
IsUsed3[num - i + n - 1] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
func(0);
cout << cnt << '\n';
}
연습문제 3.
#include <bits/stdc++.h>
using namespace std;
int n, s, cnt;
int arr[30];
void func(int cur,int tot)
{
if (cur == n)
{
if (tot == s)
cnt++;
return;
}
func(cur + 1, tot);
func(cur + 1, tot + arr[cur]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
func(0,0);
if (s == 0)
cnt--;
cout << cnt << '\n';
}
15650 . n과 M 2
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int isUsed[10];
void func(int num,int start)
{
if (num == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i <= n; i++)
{
if (isUsed[i])
continue;
arr[num] = i;
isUsed[i] = 1;
func(num + 1,i+1);
isUsed[i] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0,1);
}
기존의 n과 m에서는 arr에 값을 넣는 for문을 1부터 시작했다 이를 오름차순으로 바꿔주기 위해 인자 start를 받아 start부터 시작하게 바꿔준다 그리고 func로 호출을할때 i+1을 넘겨주면 다음 반복문은 현재 값보다 1큰값부터 백트래킹을 할것이다.
15651 N과M 3
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int isUsed[10];
void func(int num)
{
if (num == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++)
{
arr[num] = i;
func(num + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
수열 선택문제에서 중복을 허용해서 숫자를 선택하는 문제이다 기존의 isUsed배열을 통해서 값을 사용했는지 검사했으니 이부분을 지워주면 중복을허용해서 수열을 출력할수있다.
- n과 m 4
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int isUsed[10];
void func(int num,int start)
{
if (num == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i <= n; i++)
{
arr[num] = i;
func(num + 1,i);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0,1);
}
중복을 허용하고 비내림차순으로 만들어야 한다 중복을 허용하는 건 3문제에서 했으니 비내림차순으로 만들어야한다 오름차순에서 같은것도 허용가는하게 해주면된다 func(num + 1, i+1)에서 func(num + 1, i)로 바꿔주면 같은값도 들어갈수있으므로 비내림차순으로 구현이 가능하다.
15654 n과 m 5
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
int isUsed[10];
void func(int num)
{
if (num == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++)
{
if (isUsed[i])
continue;
arr[num] = input[i];
isUsed[i] = 1;
func(num + 1);
isUsed[i] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0);
}
기존의 1부터 N까지의 배열에서 배열에 직접 정수를 입력받아 문제를 해결해야한다
우선 input배열에 n번 입력을받고 arr[num] = i 로 넣어주던 부분을 arr[num] = input[i]로 변경해준다.
15655 . N과 M (6)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx, int start)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i < n; i++)
{
if (!isUsed[i])
{
arr[idx] = input[i];
isUsed[i] = 1;
func(idx + 1, i + 1);
isUsed[i] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0, 0);
}
기존의 문제에서 정수배열을 입력받은 배열로 변경해주면된다.
15656 . N과 M (7)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++)
{
arr[idx] = input[i];
func(idx + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0);
}
이문제도 위의 중복을 허용하는 문제와 동일하다 다만 정수가아닌 배열에 직접 입력을 받아서 수를 선택한다.
15657 . N과 M (8)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx,int start)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i < n; i++)
{
arr[idx] = input[i];
func(idx + 1,i);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0,0);
}
비내림차순으로 수열을 선택하기위해 func 함수의 인자로 start를 추가한다.
15663 . N과 M(9)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for (int i = 0; i < n; i++)
{
if (isUsed[i] || prev_num == input[i])
continue;
arr[idx] = input[i];
isUsed[i] = 1;
prev_num = input[i];
func(idx + 1);
isUsed[i] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0);
}
배열의 입력에 중복값을 받을수있다. 그러므로 기존의 중복을 허용하는 것을 베이스로 하면 같은 수열인 1,4,9,9를 입력받았을때(순서가 다르다고해도 정렬을 수행한다) 1,9(1) 1,9(2) 의 똑같은 수열이 두번연속해서 나올것이다 이를 방지하기위해 prev_num을 선언한다 prev_num은 자신의 idx에서 값을 채워넣은 것을 기억한다. 그렇다면 앞자리에 1이 채워진상태에서 1,4가 넘어가고 1,9가 넘어간다음 다음 9를 탐색할때 prev_num이 9인상태이므로 넘어갈것이고 다른 수가 들어갈때 이 prev_num이 초기화될것이기때문에 중복되는 수열은 선택되지않는다.
15664 . N과 M 10
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx,int start)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for (int i = start; i < n; i++)
{
if (isUsed[i] || prev_num == input[i])
continue;
arr[idx] = input[i];
isUsed[i] = 1;
prev_num = input[i];
func(idx + 1,i);
isUsed[i] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0,0);
}
위문제의 풀이에서 func의 인자로 start를 받아 비내림차순으로 수열을 선택하는것을 추가한다.
15665 . N과 M 11
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for (int i = 0; i < n; i++)
{
if ( prev_num == input[i])
continue;
arr[idx] = input[i];
prev_num = input[i];
func(idx + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0);
}
위의 문제에서 isUsed를 이용해 중복을 검사하는 부분을 빼면 중복을 허용하는 수열을 골라낼수 있다.
15666 . N과M 12
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int input[10];
bool isUsed[10];
void func(int idx,int start)
{
if (idx == m)
{
for (int i = 0; i < m; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for (int i = start; i < n; i++)
{
if ( prev_num == input[i])
continue;
arr[idx] = input[i];
prev_num = input[i];
func(idx + 1,i);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> input[i];
}
sort(input, input + n);
func(0,0);
}
비내림차인 수열을 만들어야하므로 func의 인자로 start를 추가해 비내림차순을 구현한다.
6603 . 로또
#include <bits/stdc++.h>
using namespace std;
int arr[13];
int lotto[6];
void func(int idx, int start,int len)
{
if (idx == 6)
{
for (int i = 0; i < idx; i++)
{
cout << lotto[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i < len; i++)
{
lotto[idx] = arr[i];
func(idx + 1, i + 1,len);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
while (1)
{
int len;
cin >> len;
if (len == 0)
break;
for (int i = 0; i < len; i++)
{
cin >> arr[i];
}
func(0, 0, len);
cout << '\n';
}
}
while문을통해 len을 입력받고 0이 들어올때까지 반복한다.
for문을통해 배열 arr에 len개의 숫자를 입력받고 재귀함수 func를 호출한다.
func는 6개의 숫자를 lotto에 채워놓고 start를 통해 오름차순으로 숫자를 선택한다 그리고 배열 arr의 길이를 len으로 입력받아 반복문의 최대값으로 활용한다.
1759 . 암호만들기
#include <bits/stdc++.h>
using namespace std;
char password[20];
char arr[20];
int l, c;
void func(int idx, int start)
{
if (idx == l)
{
int cntja = 0, cntmo = 0;
for (int i = 0; i < idx; i++)
{
if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u')
cntja++;
else
cntmo++;
}
if (cntja >= 1 && cntmo >= 2)
{
for (int i = 0; i < idx; i++)
{
cout << password[i];
}
cout << '\n';
}
return;
}
for (int i = start; i < c; i++)
{
password[idx] = arr[i];
func(idx + 1, i + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> l >> c;
for (int i = 0; i < c; i++)
{
cin >> arr[i];
}
sort(arr, arr + c);
func(0, 0);
}
#include <bits/stdc++.h>
using namespace std;
char password[20];
char arr[20];
int l, c;
void func(int idx, int start)
{
if (idx == l)
{
int cntja = 0, cntmo = 0;
for (int i = 0; i < idx; i++)
{
if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u')
cntja++;
else
cntmo++;
}
if (cntja >= 1 && cntmo >= 2)
{
for (int i = 0; i < idx; i++)
{
cout << password[i];
}
cout << '\n';
}
return;
}
for (int i = start; i < c; i++)
{
password[idx] = arr[i];
func(idx + 1, i + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> l >> c;
for (int i = 0; i < c; i++)
{
cin >> arr[i];
}
sort(arr, arr + c);
func(0, 0);
}
패스워드를 저장할 password와 후보 알파벳을 입력받을 arr을 선언하고 비밀번호의 길이 l과 후보군의 길이 c를 입력받는다
arr에 c만큼 입력을 받고 sort함수를 통해 사전순으로 정렬한후 func를 호출한다.
func는 start를통해 오름차순으로 순열을 선택하고 이는 중복없이 오름차순으로 l개의 순열을 구성한다 순열을 출력하기전 password를 탐색해 자음가 모음의 갯수가 조건을 만족할때만 출력을해준다.
1941 . 소문난 칠공주
#include <bits/stdc++.h>
using namespace std;
char board[5][5];
bool can_go[5][5];
bool visited[5][5];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
queue <pair<int, int>> location;
vector <int> member(25 - 7, 0);
bool location_check()
{
int mem_count =0;
while (!location.empty())
{
int x = location.front().first;
int y = location.front().second;
location.pop();
mem_count++;
for (int dir = 0; dir < 4; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
if (visited[nx][ny]) continue;
if (!can_go[nx][ny]) continue;
visited[nx][ny] = 1;
location.push({ nx,ny });
}
}
return (mem_count == 7);
}
bool team_check()
{
int Y_count = 0;
int x = 0, y = 0;
for (int i = 0; i < 25; i++)
{
if (member[i] != 1)
continue;
x = i / 5;
y = i % 5;
can_go[x][y] = true;
if (board[x][y] == 'Y')
Y_count++;
if (Y_count >= 4)
return false;
}
visited[x][y] = 1;
location.push({ x,y });
return (location_check());
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 5; i++)
{
string str;
cin >> str;
for (int j = 0; j < 5; j++)
{
board[i][j] = str[j];
}
}
for (int i = 0; i < 7; i++)
{
member.push_back(1);
}
int answer = 0;
do
{
memset(can_go, false, sizeof(can_go));
memset(visited, false, sizeof(visited));
while (!location.empty())
{
location.pop();
}
if (team_check())
{
answer++;
}
} while (next_permutation(member.begin(), member.end()));
cout << answer << '\n';
return 0;
}2차원 배열 board[5][5]에 Y,S을 입력받는다
다음 미리 0을 18개 넣어둔 벡터 member에 1을 7개 넣어 18개의 0과7개의 1들어있는 벡터를 준비한다(next_permutation을 통해 25개중에 7개를 선택한다)
다음은 do while(next_permutaion)을 통해 백트래킹을 한다.
우선 can_go(해당하는 멤버값이 1인지 즉 칠공주의 멤버인지를 저장)
visited(BFS를 통해 탐색할때 이미 방문한곳은 방문하지 않기 위함)
location(BFS에 사용하기위한 큐)
셋을 초기화해준후
team_check() 함수를 호출한다 이 함수가 true를 호출하면 해당 순열이 정답으로 인정되는경우다. team_check()함수로 들어가면
우선 25개의 칸을 차례대로 탐색하며 member[i]가 1인칸 즉 칠공주의 멤버인 칸만을 탐색한다.
해당 칸의 can_go를 true로 변경해주고 y인지 검사해 y_count를 늘려준다.(칠공주의 멤버가 Y가 4명이상이면 안되기때문에 4명이라면 이어지는지 검사하지않고 false를 리턴해준다)
반복문이 끝나면 x,y에는 마지막에 해당하는 칠공주 멤버의 x,y값이 들어있을것이고 이를 location큐에 넣어주고 해당 멤버들이 이어져있는지를 검사하는 함수 location_check() 함수를 호출한다.
location_check()는 BFS를통해 해당칸이 방문하지않은칸이고 멤버인칸인지를 상하좌우로검사하며 7개의 멤버가 서로 이어져있는지를 검사해 리턴해준다.
이렇게 true가 반환되면 정답인경우이므로 answer++를하고 마지막으로 정답을 출력한다.
16987 . 계란으로 계란치기
#include <bits/stdc++.h>
using namespace std;
int dur[8], weight[8];
int n, ans = 0;
void DFS(int index)
{
if (index >= n)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (dur[i] <= 0) cnt++;
}
ans = max(ans, cnt);
return;
}
if (dur[index] > 0)
{
bool flag = false;
for (int i = 0; i < n; i++)
{
if (i == index || dur[i] <= 0) continue;
dur[i] -= weight[index];
dur[index] -= weight[i];
flag = true;
DFS(index + 1);
dur[i] += weight[index];
dur[index] += weight[i];
}
if (flag == false) DFS(n);
}
else
{
DFS(index + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> dur[i] >> weight[i];
}
DFS(0);
cout << ans << '\n';
}내구도를 저장할 배열 dur와 무게를 저장할 배열 weight를 선언한다 배열의 크기는 최대계란 갯수인 8로 한다.
다음 계란의 갯수 n을 입력받아 for문으로 각 배열에 값을 넣은뒤 DFS함수를 호출한다.
DFS함수는 우선 종료조건으로 index가 N보다 같거나 큰지 (즉 마지막 계란까지 모두쳤거나 칠 계란이 없다) 검사한다 종료조건으로 들어온경우 dur 배열중에 0보다 작은 값의 갯수를 cnt에 저장해 현재 최대값인 ans와 비교해 ans에 저장해준다.
종료조건이 아닌경우 백트래킹을 통해 문제를 해결한다. 우선 현재 인덱스의 계란의 내구도 0보다 큰지 검사한다 작을경우 깨진계란으로는 다른 계란을 칠수 없기 때문에 DFS(index + 1)을 호출하고 종료한다. 칠수있는 계란일경우 자신부터 오른쪽의 계란을 모두 쳐본다. 이때 하나라도 칠수있는 계란이 있는지 flag를 통해 검사한다 칠계란이 아무것도 없는것은 더이상 백트래킹을 할필요가없다는 뜻이기때문에 DFS(N)을 호출해 종료조건으로 넘어간다.
18809 . 가든
#include <bits/stdc++.h>
using namespace std;
int board[55][55];
int N, M, G, R;
vector <pair<int, int>> cand;
vector <int> loc;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int solve()
{
pair<int, int> st[55][55];
queue<pair<int, int>> q;
for (int i = 0; i < cand.size(); i++)
{
if (loc[i] == 0) continue;
int x = cand[i].first;
int y = cand[i].second;
q.push({ x,y });
st[x][y] = { 0,loc[i] };
}
int cnt = 0;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
int time = st[x][y].first;
int who = st[x][y].second;
q.pop();
if (who == 3) continue;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (board[nx][ny] == 0) continue;
if (st[nx][ny].second == 0)
{
st[nx][ny] = { time + 1, who };
q.push({ nx,ny });
}
else if (st[nx][ny].second == 1)
{
if (who == 2 && time + 1 == st[nx][ny].first)
{
cnt += 1;
st[nx][ny].second = 3;
}
}
else if (st[nx][ny].second == 2)
{
if (who == 1 && time + 1 == st[nx][ny].first)
{
cnt += 1;
st[nx][ny].second = 3;
}
}
}
}
return cnt;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> board[i][j];
if (board[i][j] == 2)
{
cand.push_back({ i,j });
loc.push_back(0);
}
}
}
for (int i = 0; i < loc.size(); i++)
{
if (G > 0)
{
loc[i] = 1;
G -= 1;
}
else if (R > 0)
{
loc[i] = 2;
R -= 1;
}
}
sort(loc.begin(), loc.end());
int ans = 0;
do
{
ans = max(ans, solve());
} while (next_permutation(loc.begin(), loc.end()));
cout << ans << '\n';
}18809 . 가든
#include <bits/stdc++.h>
using namespace std;
int board[55][55];
int N, M, G, R;
vector <pair<int, int>> cand;
vector <int> loc;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int solve()
{
pair<int, int> st[55][55];
queue<pair<int, int>> q;
for (int i = 0; i < cand.size(); i++)
{
if (loc[i] == 0) continue;
int x = cand[i].first;
int y = cand[i].second;
q.push({ x,y });
st[x][y] = { 0,loc[i] };
}
int cnt = 0;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
int time = st[x][y].first;
int who = st[x][y].second;
q.pop();
if (who == 3) continue;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (board[nx][ny] == 0) continue;
if (st[nx][ny].second == 0)
{
st[nx][ny] = { time + 1, who };
q.push({ nx,ny });
}
else if (st[nx][ny].second == 1)
{
if (who == 2 && time + 1 == st[nx][ny].first)
{
cnt += 1;
st[nx][ny].second = 3;
}
}
else if (st[nx][ny].second == 2)
{
if (who == 1 && time + 1 == st[nx][ny].first)
{
cnt += 1;
st[nx][ny].second = 3;
}
}
}
}
return cnt;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> G >> R;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> board[i][j];
if (board[i][j] == 2)
{
cand.push_back({ i,j });
loc.push_back(0);
}
}
}
for (int i = 0; i < loc.size(); i++)
{
if (G > 0)
{
loc[i] = 1;
G -= 1;
}
else if (R > 0)
{
loc[i] = 2;
R -= 1;
}
}
sort(loc.begin(), loc.end());
int ans = 0;
do
{
ans = max(ans, solve());
} while (next_permutation(loc.begin(), loc.end()));
cout << ans << '\n';
}baord,n,m,g,r을 선언하고 입력받는다.
vector cand는 배양액을 뿌릴수있는 땅의 좌표를 저장할 벡터이고
vector loc는 next_permutation을통해 순열을 구성하고 배양액을 뿌릴땅을 결정하기위한 벡터이다.
다음 이중 for문을 통해 board에 입력을받으면서 만약 2 (배양액을 뿌릴수 있는 땅)이 입력된경우
다음 loc벡터에는 배양액을 뿌릴수있는 땅의 수만큼 0들어가있을것이고 최소 R+C의 값을 가질것이다. 해당 0을을 G만큼 1로 R만큼 2로변경해준다 그렇다면 R+G에 추가로 여분의 땅은 0으로 표시되어 이벡터에 등록될것이다. 다음 next_permutaion은 사전순으로 정렬되어있어야기하기 때문에 sort함수를 통해 정렬해주고
다음 do while문을 통해 현재 답 ans와 sovle()함수의 반환값을 비교한다.
solve함수는 우선 보드와 같은크기의 st배열을 선언한다 인자는 pair<int,int>인데 first는 시간을 second는 배양액의 색깔을 의미한다( 0 안뿌려짐, 1 그린,2 레드, 3꽃)
큐 q는 BFS를 위한 큐로 사용한다 다음 cand.size() (배양액을 뿌릴수있는 땅의 갯수) 만큼 반복문을 시작한다.
이때 loc는 순서대로 순열이 들어가있을것이고 우리는 1과2에 해당하는 칸에 배양액을 뿌려줄것이다
x,y를 선언하여 해당 배양액을 뿌릴수있는 칸의 좌표를 큐에 넣어고 배열 st의 값을{0(시간),loc[i] (뿌릴 배양액의 색)} 을 넣어준다
다음 BFS를 통해 배양액을 퍼트린다.
큐에서 값을 꺼내고 만약 꽃일경우에는 배양액을 퍼트리지않으므로 넘어간다.
BFS를통해 넘어간 칸이 0일경우 st값을 해당하는 경우로 바꿔주고
배양액 r이뿌려진칸인경우 넘어가는칸이 g이고 시간값이 현재 시간 +1 같다면 꽃으로 표시해주고 cnt를 1늘려준다. g도 똑같이 해준다.
cnt를 리턴하고 ans와비교를한다. 마지막으로 ans 출력하면 문제를 해결할수있다.
1799 . 비숍
#include <bits/stdc++.h>
using namespace std;
int N;
int ans[2];
int chess[11][11];
int l[20];
int r[20];
void tracking(int row, int col, int count, int color)
{
if (col >= N)
{
row++;
if (col % 2 == 0) col = 1;
else col = 0;
}
if (row >= N)
{
ans[color] = max(ans[color], count);
return;
}
if (chess[row][col] && !l[col - row + N - 1] && !r[row + col])
{
l[col - row + N - 1] = r[row + col] = 1;
tracking(row, col + 2, count + 1, color);
l[col - row + N - 1] = r[row + col] = 0;
}
tracking(row, col + 2, count, color);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> chess[i][j];
}
}
tracking(0, 0, 0, 0);
tracking(0, 1, 0, 1);
cout << ans[0] + ans[1] << '\n';
}문제의핵심은 홀수칸과 짝수칸을 따로보는것이다 체스판처럼 처음칸은 흰색 다음칸은 검은색으로 순차적으로 칠해 체크판을 만든다고 할때 비숍 즉 대각선 사정거리에는 같은색의 칸만 해당된다.
우선 보드로 사용할 chess에 N*N 만큼 입력을 받은뒤
tracking 함수를 호출한다.
tracking 함수의 1,2번째는 각각 행과 열을 의미하고 count는 비숍을 놓은 숫자 color는 시작한칸의 색을 의미한다(정답을 흑과 백따로 저장해서 더할것이기때문에 어느 정답칸에 넣을지 결정할때 사용)
우린 함수인자를 통해서는 col값만 늘려줄것이기때문에 만약 col이 N 이상의 값으로 들어온다면 col이 2의 배수일경우 다음은 1부터 시작하고 아닐경우는 0부터 시작한다.
다음 row 즉 행이 N을 넘어선경우 ans에 max를통한 값비교로 정답을 넣어준다.
다음은 해당칸에 비숍을 놓을지를 판단한다.
비숍을 놓기위해선 우선 chess판에 비숍을 놓을수있는칸이어야하고 왼쪽대각선과 오른쪽대각선에 해당하는 대각선에 비숍이 놓여있어선안된다. 이를확인후 백트래킹을 통해 대각선에 값을 넣어주고 트래킹 함수를 호출하고 0으로 만든다(이때 비숍을 놓은경우이므로 count를 1늘려준다.)
다음은 비숍을 놓지않았기떄문에 카운트값을 증가시키지않고 col값만 2증가시켜 트래킹 함수를 호출한다.
마지막으로 ans[0]과 ans[1]을 더하면 정답을 구할수있다.
Author And Source
이 문제에 관하여(0x0C강 - 백트래킹), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jacod2/0x0C강-백트래킹저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
