#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
while (1) {
cin >> n;
if (n == 0) return 0;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
for (int i = 0; i < n; i++) {
if (i < 6) Sel[i] = 0;
else Sel[i] = 1;
}
do {
for (int j = 0; j < n; j++) {
if (!Sel[j]) cout << a[j] << ' ';
}
cout << '\n';
} while (next_permutation(Sel, Sel + n));
cout << '\n';
}
return 0;
}
2. 백트래킹 활용 구현
마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.
조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.
#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
//여기서 수열의 길이 k
if (k == 6) {
for (int i = 0; i < k; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
if (k == 0) st = 0; //0일때 초기화
for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
if (!isused[i]) {
isused[i] = true;
arr[k] = num[i];
st = i;
func(k + 1);
isused[i] = false;
}
}
}
int main(void) {
while (1) {
cin >> n;
if (n == 0) break;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n);
func(0);
cout << '\n';
}
}
기본적인 접근은 불을 먼저 확산시킬 것인가, 사람을 먼저 움직일 것인가를 결정하는 것이다.
1. 불의 확산 이후 사람의 이동
불을 먼저 확산시키면 사람의 위치가 지워질 가능성이 높다. 따라서 사람의 시작 위치를 미리 관리해주어야 한다.
이후에는 사람의 이동거리(매 초 사람의 위치)를 따로 둘 것이기 때문에 초반에 불의 이동에 의해서 @의 위치가 손실되는 것만 신경써주면 이후로는 신경쓸 부분이 없다. 즉 위에서 신경써야 할 부분이라고 언급한 2번 조건이 상관 없어지는 것이다.
당연하게도 불을 먼저 확산시켰으므로 불이 붙으려는 칸으로는 당연하게 이동할 수 없다. 구현을 그렇게 했으니까.
2. 사람의 이동 이후 불의 확산
이 방식은 먼저 사람의 이동을 고려한다. 당연하게도 이동하려는 곳은 비어있는(불도 벽도 아닌) 곳이어야 한다.
그리고 그 이동하려는 곳의 4방향을 미리 탐색해서 불이 있는지 없는지를 확인해야 한다. 이것으로 신경써야 할 부분 1을 피할 수 있다.
즉 사람의 이동을 구현하는 데에 두 단계가 필요하다는 것이다.
또한 사람의 이동을 먼저 구현했기 때문에, 이미 이동한 뒤에 불이 확산하는 것이므로 원래 사람이 있던 자리에 불이 번지는 것은 이제 상관이 없어진다. 이렇게 신경써야 할 부분 2를 해결할 수 있다.
두 가지 모두 생각해 본 결과, 1의 구현이 더 간단한 것 같았으므로 1번으로 구현 방향을 잡았다.
#include<iostream>
#include<queue>
using namespace std;
int Col, Row, dis[1001][1001]; //dis로 사람의 매초 위치(그 지점까지 최단거리)를 관리
char m[1001][1001]; //빌딩 상태
bool Fire[1001][1001]; //불의 존재 여부 관리
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
queue<pair<int, int> > fireQ; //불의 번짐을 관리할 큐
queue < pair<int, int> > q; //사람의 이동을 관리할 큐
void Fbfs() {
while (!q.empty()) { //사람이 움직일 위치가 없으면 더 이상의 진행이 무의미
int num = fireQ.size(); //매 초 있던 불꽃으로만 확산 진행
while (num--) {
pair<int, int> cur = fireQ.front();
fireQ.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) continue;
if (m[nr][nc] == '#' || Fire[nr][nc]) continue; //벽 or 이미 불이 존재하는 곳이면 continue
//printf("\n%d %d 추가\n", nr, nc);
fireQ.push({ nr, nc });
Fire[nr][nc] = true;
m[nr][nc] = '*';
}
}
int Run = q.size(); //불과 마찬가지로 매초 한칸씩 움직이게 통제
while (Run--) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) {
//탈출처리 -> 건물 끝까지 가는데 n초 걸렸고, 이제 넘어가니까 +1
cout << dis[cur.first][cur.second] + 1 << '\n';
return;
}
if (dis[nr][nc] >= 0 || m[nr][nc] != '.')continue; //이미 지나온 길이거나 이동할 수 있는 길이 아니면 continue
q.push({ nr, nc });
dis[nr][nc] = dis[cur.first][cur.second] + 1;
}
}
}
cout << "IMPOSSIBLE" << '\n';
}
void init() {
for (int i = 0; i < Row; i++) {
for (int j = 0; j < Col; j++) {
dis[i][j] = -1; // 0이상이면 사람이 거쳐간 상태(방문 완료)
Fire[i][j] = false;
}
}
while (!q.empty()) q.pop(); //탈출 조건에서 큐가 비지 않았는데 함수가 종료됨
while (!fireQ.empty()) fireQ.pop();
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> Col >> Row;
init(); //TC가 여러개, 큐를 완전히 비우지 않고 끝내는 경우도 있으므로 큐도 초기화
for (int i = 0; i < Row; i++) {
for (int j = 0; j < Col; j++) {
cin >> m[i][j];
if (m[i][j] == '@') { //사람의 시작 위치를 담아둬야함. 불이 덮어 쓰기 때문에
q.push({ i, j });
dis[i][j]++;
}
}
}
for (int i = 0; i < Row; i++) {
for (int j = 0; j < Col; j++) {
if (m[i][j] == '*' && !Fire[i][j]) {
fireQ.push({ i, j });
Fire[i][j] = true;
}
}
}
Fbfs();
}
return 0;
}
정수들로 만들 수 있는 길이가 1 이상인 부분 수열들을 구한다. 그리고 그 부분수열들의 합이 처음에 입력받은 S와 같은 부분수열의 개수를 구하면 되는 문제이다.
우선 N개의 숫자를 입력받았다고 가정하면, 1개, 2개, 3개 ... N개로 만들 수 있는 부분수열을 모두 구해야 한다.
그리고 매 부분수열마다 합을 계산해서 그 합이 s인지 아닌지 판단해주면 되는 문제이다.
즉 조합으로 바꿔서 생각할 수 있고, n이 20 이하로 작으니 백트래킹을 해도 무방하다.
직접 재귀로 구현할 수도 있지만 next_permutation을 이용해서 구현했다.
Sel 배열을 우선 만들어 둔다. 가령 6개 중에 4개를 조합으로 뽑는다면,
Sel 배열은 0, 0, 0, 0, 1 1 이렇게 두고 if(!Sel[i]) 일 때 수열이 만들어지게 된다.
이를 이용해서 1개부터 n개까지 부분수열을 구해주면 되겠다.
#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a[20], Sum = 0, Sel[20], cnt = 0;
int main(void) {
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < 20; i++)
Sel[i] = 1;
for (int i = 0; i < n; i++) {
Sel[i] = 0; //하나씩 0으로 바꿈
do {
Sum = 0;
for (int j = 0; j < n; j++) {
if (!Sel[j]) Sum += a[j];
//if (!Sel[j]) cout << a[j] << ' ';
}
if (Sum == s) cnt++;
} while (next_permutation(Sel, Sel + n));
}
cout << cnt << '\n';
return 0;
}