[바킹독의 실전 알고리즘] 복습 - 0x0C

오젼·2025년 7월 2일
알고리즘
0

[바킹독의 실전 알고리즘]

목록 보기
21/23

0x0C 백트래킹

"현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법"

-> 난 지금 g++로 컴파일 중이었는데 

alias g++
g++='g++ -std=c++17 -pedantic'

이렇게 컴파일 옵션을 설정하고 있었다. 이 경우 최적화 없이 디버깅 모드로 컴파일 되는 거였음.

g++ -O2

그래서 이렇게 해주면 된다.

g++ 기본 설정은 디버그용(-O0)이라 느립니다. 성능을 최대로 끌어내기 위해선 Release 모드, 즉 최적화 옵션을 활성화해야 합니다.

-> 출처

시간 측정은 time으로 해주면 된다.

15649 | N과 M (1)

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

int arr[10];
bool isused[10];

int n, m;

void f(int k) {
	if (k == m) {
		for (int i = 0; i < m; ++i) cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i) {
		if (isused[i]) continue;
		arr[k] = i;
		isused[i] = 1;
		f(k + 1);
		isused[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	f(0);
}

뭔가 이제 감으로는 확실히 알겠는데.. 내가 풀어놓고도 어케 푼 건지 모르겠다

일단 수열이 각 상태가 1부터 n까지 바뀌어야 하는 건 알겠음 그래서 for (int i = 1; i <= n; ++i).

그리고 각 시작점에 대해서 arr을 채워나가야 함. 이때 중복체크를 해줘야 하기 때문에 arr[k] = i; isused[i] = 1;을 해줌.

그리고 다음 k+1번째 배열을 채워주기 위해 f(k+1)로 들어감.

이때 이미 i가 사용된 경우를 피해줘야 하기 때문에 if(isused[i]) continue;를 처음에 넣어줌.

그렇게 타고타고 가다가 k == m이 되는 순간 채워진 배열을 출력하고 return 돼야 함.

들어갔던 함수를 나오면서 isused[i] = 0; 으로 바꿔줘야 함. 내가 쓰인 순간들은 모두 끝났기 때문에.

🔁 너의 설명을 기반으로 구조화한 정리
1. f(k)는 수열의 k번째 자리를 채우는 함수이다.
2. for (int i = 1; i <= n; ++i)를 통해 1부터 n까지의 숫자를 하나씩 넣어본다.
3. 이미 사용한 숫자는 isused[i] == true이므로 continue로 건너뛴다.
4. 사용하지 않은 숫자라면 arr[k] = i, isused[i] = true로 해당 숫자를 채운다.
5. f(k + 1)을 호출해서 다음 자리를 채운다.
6. 함수가 끝나고 나면 다시 isused[i] = false로 되돌려서 다른 경우의 수를 위한 준비를 한다.
7. k == m이 되면 m개의 수를 모두 고른 상태이므로 출력하고 리턴한다.

9663 | N-Queen

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

int cnt;
int n;
bool isused[3][35];

void f(int r) {
	if (r == n) {
		++cnt;
		return;
	}

	for (int c = 0; c < n; ++c) {
		if (isused[0][c] || isused[1][r + c] || isused[2][(r - c) + (n - 1)])
			continue;
		isused[0][c] = 1;
		isused[1][r + c] = 1;
		isused[2][(r - c) + (n - 1)] = 1;
		f(r + 1);
		isused[0][c] = 0;
		isused[1][r + c] = 0;
		isused[2][(r - c) + (n - 1)] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	f(0);
	cout << cnt;
}

N-Queen은 언제 안 까먹을까...
isused 배열이 3개 필요하다. |, \, /. 즉 수직, 대각선1, 대각선2를 보고 가지치기를 결정하기 위해.

일단 |는 쉽다. 내 col을 그대로 인덱스로 사용해주면 된다.

/도 쉽다. 내가 x,y라면 (x+1, y-1), (x+2, y-2) ... 이런식으로 대각선 좌표가 형성되니까 r+c를 인덱스로 사용해주면 된다.

\는 내가 x,y라면 (x+1, y+1), (x+2, y+2) ... 이런식으로 좌표가 형성된다. r-c가 같게 되는 건데 이때 음수값이 나올 수 있다. 범위가 (-(n-1) ~ +(n-1))이 된다. 왜냐면 (0, n-1) ~ (n-1, 0)이니까.

그래서 보정을 위해 r-c + n-1을 인덱스로 사용해준다.

1182 | 부분수열의 합

부분 수열은 내가 포함 돼있냐, 안 돼있냐로 타고타고 들어가야 함!

그리고 공집합도 포함된다는 것 주의

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

int n, s, cnt;
int arr[20];

void f(int cur, int sum) {
	if (cur == n) {
		if (sum == s) ++cnt;
		return;
	}

	f(cur + 1, sum);			 // 내가 포함되지 않음
	f(cur + 1, sum + arr[cur]);	 // 내가 포함 됨
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	f(0, 0);
	if (s == 0) --cnt;	// 공집합의 합도 0이므로
	cout << cnt;
}

15650 | N과 M (2)

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

int n, m;
int ans[10];

void f(int k, int start) {
	if (k == m) {
		for (int i = 0; i < m; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = start; i <= n; ++i) {
		ans[k] = i;
		f(k + 1, i + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	f(0, 1);
}

isused 불필요하다는 것 주의!!
이전에 출력된 원소는 자연스럽게 쓰이지 않게 된다.

isused 없이도 조합을 만들 수 있는 이유는,
재귀마다 start를 이전 수 + 1로 올려주기 때문에
이미 선택된 수보다 작은 수는 다시 고려되지 않음.
따라서 자연스럽게 중복 없이 오름차순 조합이 생성된다.

next_permutation 버전

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

int n, m;
int ans[10];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	vector<int> a;
	for (int i = 0; i < n; ++i) a.push_back(i < m ? 0 : 1);

	do {
		for (int i = 0; i < n; ++i) {
			if (a[i] == 0) cout << i + 1 << ' ';
		}
		cout << '\n';
	} while (next_permutation(a.begin(), a.end()));
}

next_permutation

bool next_permutation(begin, end);

현재 배열을 "다음 사전순 순열"로 바꿔줌
리턴값:
true: 다음 순열이 존재해서 바꿔줬다는 뜻
false: 더 이상 다음 순열이 없다는 뜻 (가장 큰 순열이었다)

조합을 만들기 위해선 뽑을 위치가 0, 안 뽑을 위치가 1이라 생각하고 진행해야 한다.

✅ 주의할 점

입력이 꼭 사전순(오름차순) 으로 정렬되어 있어야
→ 모든 순열을 빠짐없이 생성할 수 있음

// 3개 뽑기 → 0: 뽑음, 1: 안 뽑음
vector<int> a = {0, 0, 0, 1, 1}; // 5C3
do {
    for (int i = 0; i < a.size(); ++i)
        if (a[i] == 0) cout << i + 1 << ' ';
    cout << '\n';
} while (next_permutation(a.begin(), a.end()));

15651 | N과 M (3)

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

int arr[10];
int n, m;

void f(int k) {
	if (k == m) {
		for (int i = 0; i < m; ++i) cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; ++i) {
		arr[k] = i;
		f(k + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	f(0);
}

간단.

next_permutation으로 풀 수 없음.
중복이 허용된 중복 순열이기 때문에.

next_permutation()은
입력된 배열의 순열을 만드는 함수
즉, 고정된 원소를 섞는 것만 가능하지
새로운 값을 추가하거나 중복을 생성하지는 못함

15652 | N과 M (4)

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

int n, m;
int arr[10];

void f(int k, int st) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = st; i <= n; ++i) {
		arr[k] = i;
		f(k + 1, i);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	f(0, 1);
}

간단

15654 | N과 M (5)

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

int n, m;
int arr[10], ans[10];
bool isused[10];

void f(int k) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (isused[i]) continue;
		ans[k] = arr[i];
		isused[i] = 1;
		f(k + 1);
		isused[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);

	f(0);
}

간단

15655 | N과 M (6)

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

int n, m, arr[10], ans[10];

void f(int k, int st) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = st; i < n; ++i) {
		ans[k] = arr[i];
		f(k + 1, i + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0, 0);
}

간단

15656 | N과 M (7)

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

int arr[10], ans[10], n, m;

void f(int k) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i) {
		ans[k] = arr[i];
		f(k + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0);
}

간단

15657 | N과 M (8)

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

int n, m, arr[10], ans[10];

void f(int k, int st) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = st; i < n; ++i) {
		ans[k] = arr[i];
		f(k + 1, i);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0, 0);
}

간단

15663 | N과 M (9)

틀린 버전

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

int n, m, arr[10], ans[10];
bool isused[10];

void f(int k) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (isused[i]) continue;
		if (ans[k] == arr[i]) continue;
		isused[i] = 1;
		ans[k] = arr[i];
		f(k + 1);
		isused[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0);
}

반례

4 4
1 1 1 2

지금 나는 ans[k]가 이미 arr[i]와 같은 값으로 채워져 있었다면 이를 피해 중복을 방지하려 했었다.

이러면 문제가

1 1 1 2
1 1 2 1 (여기까진 ok. 백트래킹으로 k == 1로 감)
1 2 1 1 (이걸 해야하는데 이전에 있던 ans[k] 때문에 못 한다 ans[3] == arr[i]가 돼버림)

같은 depth에 있을 때 중복으로 사용하는 경우만 막아야 하는데 다른 depth에서 채웠던 값도 중복이면 오답으로 여겨버려서 문제가 생겼던 것.

같은 depth의 중복을 피하기 위해 last 값을 두고 ans[k]를 채웠을 때마다 update가 되게 해서 검사를 한다.

정답 버전

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

int n, m, arr[10], ans[10];
bool isused[10];

void f(int k) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	int last = 0;
	for (int i = 0; i < n; ++i) {
		if (isused[i]) continue;
		if (last == arr[i]) continue;
		isused[i] = 1;
		ans[k] = arr[i];
		last = arr[i];
		f(k + 1);
		isused[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0);
}

15664 | N과 M (10)

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

int n, m, arr[10], ans[10];
bool isused[10];

void f(int k, int st) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	int last = 0;
	for (int i = st; i < n; ++i) {
		if (isused[i] || last == arr[i]) continue;
		isused[i] = 1;
		ans[k] = last = arr[i];
		f(k + 1, i + 1);
		isused[i] = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	f(0, 0);
}

sort 놓치지 말기!

15665 | N과 M (11)

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

int n, m, arr[10], ans[10];

void f(int k) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; ++i) {
		ans[k] = arr[i];
		f(k + 1);
	}
}

bool in(int k, int size) {
	for (int i = 0; i < size; ++i) {
		if (k == arr[i]) return true;
	}
	return false;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		if (!in(k, cnt)) arr[cnt++] = k;
	}
	n = cnt;
	sort(arr, arr + n);
	f(0);
}

존재 여부 검사

bool exist[10001];

if (exist[k]) continue;
exist[k] = 1;
arr[cnt++] = k;

이렇게 O(1)로 가능하단 것도 잊지 말기

15666 | N과 M (12)

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

int n, m, arr[10], ans[10];
bool exist[10001];

void f(int k, int st) {
	if (k == m) {
		for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = st; i < n; ++i) {
		ans[k] = arr[i];
		f(k + 1, i);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		if (exist[k]) continue;
		arr[cnt++] = k;
		exist[k] = 1;
	}

	n = cnt;
	sort(arr, arr + n);
	f(0, 0);
}

6603 | 로또

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

int arr[15], ans[6], k;

void f(int d, int st) {
	if (d == 6) {
		for (int i = 0; i < d; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = st; i < k; ++i) {
		ans[d] = arr[i];
		f(d + 1, i + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (1) {
		cin >> k;
		if (k == 0) break;
		for (int i = 0; i < k; ++i) cin >> arr[i];
		f(0, 0);
		cout << '\n';
	}
}

쉬움

1759 | 암호 만들기

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

int l, c;
char arr[20], skip[20];

int aeiou() {
	int cnt = 0;
	for (int i = 0; i < c; ++i) {
		if (skip[i]) continue;
		char ch = arr[i];
		if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
			++cnt;
	}
	return 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);

	for (int i = l; i < c; ++i) skip[i] = 1;

	do {
		int cnt = aeiou();
		if (cnt == 0 || l - cnt < 2) continue;

		for (int i = 0; i < c; ++i) {
			if (skip[i] == 0) cout << arr[i];
		}
		cout << '\n';
	} while (next_permutation(skip, skip + c));
}

쉬움

1941 | 소문난 칠공주

으으... 어려웠다.
이건 그냥 25C7을 하고 조건에 맞는지, 아닌지 확인해줬어야 했던 문제.

ver 1

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

char student[8][8];
int skip[25], ans;
bool vis[8][8];

queue<pair<int, int> > q;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

void init_vis() {
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) {
			if (skip[i * 5 + j]) continue;
			vis[i][j] = 0;
			if (q.empty()) {
				q.push({i, j});
				vis[i][j] = 1;
			}
		}
	}
}

bool check_around() {
	init_vis();
	int cnt = 0;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		++cnt;
		for (int d = 0; d < 4; ++d) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
			if (skip[nx * 5 + ny] || vis[nx][ny]) continue;
			q.push({nx, ny});
			vis[nx][ny] = 1;
		}
	}
	return cnt == 7;
}

bool check_count() {
	int cnt = 0;
	for (int i = 0; i < 25; ++i) {
		if (skip[i]) continue;
		if (student[i / 5][i % 5] == 'S') ++cnt;
	}
	return cnt >= 4;
}

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 >> student[i][j];
	}

	for (int i = 7; i < 25; ++i) skip[i] = 1;
	do {
		if (!check_count()) continue;
		if (!check_around()) continue;
		++ans;
	} while (next_permutation(skip, skip + 25));
	cout << ans;
}

// 25C7 을 하고 과반인지, 인접했는지 확인

ver2

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

char student[5][5];
int gang[7], board[5][5], ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

bool bfs_check(int r, int c) {
	queue<pair<int, int> > q;
	bool vis[5][5] = {};

	q.push({r, c});
	vis[r][c] = 1;
	int cnt = 0;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		++cnt;

		for (int d = 0; d < 4; ++d) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
			if (!board[nx][ny] || vis[nx][ny]) continue;
			q.push({nx, ny});
			vis[nx][ny] = 1;
		}
	}
	return cnt == 7;
}

void dfs(int k, int st, int soms) {
	if (k == 7) {
		if (soms >= 4 && bfs_check(gang[0] / 5, gang[0] % 5)) ++ans;
		return;
	}

	for (int i = st; i < 25; ++i) {
		gang[k] = i;
		board[i / 5][i % 5] = 1;
		// soms += 1 하지 않게 조심
		dfs(k + 1, i + 1, soms + (student[i / 5][i % 5] == 'S'));
		board[i / 5][i % 5] = 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 >> student[i][j];
	}
	dfs(0, 0, 0);
	cout << ans;
}

if (student[i / 5][i % 5] == 'S') soms += 1;
을 하고
dfs(k+1, i+1, soms); 를 해서 틀렸었음.

soms += 1을 해버리면 내가 쓰이지 않는 다음 조합에도 영향을 미쳐버림.

soms값을 업데이트 하지 말고
dfs( , , soms + (student[i / 5][i % 5] == 'S'))를 해줘야 함.

그리고 vis 배열 지역변수로 하면 매번 초기화할 필요 없음.

이 문제를 어떻게 빨리 파악할 수 있을까..

좋은 질문이에요. 이건 알고리즘 실력과 문제 경험 모두가 필요한 감각적인 부분인데, 체계적으로 연습하면 충분히 길러질 수 있어요. 아래에 당신이 궁금해하는 핵심들을 단계별로 설명해볼게요.

✅ 1. "이 문제는 나이브하게 풀어야 하는구나"를 어떻게 알 수 있을까?

🔎 핵심은 **"조합 + 조건 검사"**라는 구조를 빨리 캐치하는 것.

이 문제는 다음과 같은 단서를 가지고 있어요:

조건힌트가 되는 이유
5x5 보드에서 7명을 선택한다→ 25명 중 7명 선택: 조합 (25C7)
인접해야 한다 (상하좌우)→ 선택 후 BFS/DFS로 연결성 검사
S가 최소 4명 이상→ 선택한 7명 중 조건 필터링

💡 그래서 판단 흐름은 이래야 해요:

“선택된 7명을 기준으로 조건을 검사한다” → 그러면 일단 7명을 모두 선택해보고 → 그때마다 조건을 검사하면 되겠다

이 패턴은 꽤 자주 나옵니다.

✅ 2. "나이브하게 가능하겠다"는 어떻게 확신할까?

🌟 시간 복잡도 추정이 중요합니다

25C7 = 약 480,000
→ 각 조합마다 조건 확인 (BFS: O(7)) → 총 480,000 * 7 = 약 300만 연산
  • 백준 기준: 1초 = 약 1억 연산 가능 → 충분히 가능

💡 즉,

  • 조합 수 계산 + 각 경우의 처리 시간이 충분히 작다 → 나이브하게 해도 된다

✅ 3. 비슷한 유형 문제에서 써먹을 수 있는 판단 기준

상황전략
제한된 크기 (예: 5x5, 최대 25개 등)완전탐색, 조합, 백트래킹을 적극 의심
전체 경우의 수가 100만 이하나이브 가능성 높음
선택 후 조건 검사 (연결, 비율 등)조합 후 BFS/DFS로 조건 체크
여러 조건이 겹칠 경우"선택 먼저, 조건 나중" 패턴을 적용

✅ 4. 더 빠르게 눈치채는 팁

  • "7명 중 4명 이상이 S" → 선택된 집합의 구성 검사
  • "인접" → 연결성 검사 (BFS/DFS)
  • 보드 크기 작음 (5x5) → 완전탐색 OK
  • 조합 수 추정이 중요 → NCr은 N^r보다 빠르게 줄어듦

✅ 마무리 요약

질문답변 요약
어떻게 이런 문제는 완전탐색임을 알 수 있을까?입력 크기 작음(5x5), 조건 검사 필요(S 개수, 인접성) → 조합 후 검사 전략
어떻게 눈치챌 수 있을까?전체 경우 수(25C7) 계산 → 시간 내 가능 → 나이브 가능성 판단
반복적으로 연습할 수 있는 기준은?"작은 크기 + 조합/연결 조건 → 조합+검사 패턴"을 암기

16987 | 계란으로 계란치기

ver 1

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

#define X first
#define Y second

int n, vs[10], ans;
pair<int, int> arr[10];

int break_eggs() {
	pair<int, int> eggs[10];
	for (int i = 0; i < n; ++i) eggs[i] = arr[i];

	for (int i = 0; i < n; ++i) {
		if (eggs[i].X <= 0 || eggs[vs[i]].X <= 0) continue;
		eggs[i].X -= eggs[vs[i]].Y;
		eggs[vs[i]].X -= eggs[i].Y;
	}

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (eggs[i].X <= 0) ++cnt;
	}
	return cnt;
}

void dfs(int k) {
	if (k == n) {
		ans = max(ans, break_eggs());
		return;
	}
	for (int i = 0; i < n; ++i) {
		if (i == k) continue;
		vs[k] = i;
		dfs(k + 1);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i) cin >> arr[i].X >> arr[i].Y;
	dfs(0);
	cout << ans;
}

완전탐색. 단순 순열로 풂. 나이브한 풀이.
통과이긴 하다. 근데 이렇게 풀면 안 될 듯ㅠ

ver 2 틀린버전

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

#define X first
#define Y second

int n, ans, cnt;
pair<int, int> arr[10];

void dfs(int k) {
	if (k == n) {
		ans = max(ans, cnt);
		return;
	}
	for (int i = 0; i < n; ++i) {
		if (i == k || arr[k].X <= 0 || arr[i].X <= 0) continue;
		arr[k].X -= arr[i].Y;
		arr[i].X -= arr[k].Y;
		if (arr[k].X <= 0) ++cnt;
		if (arr[i].X <= 0) ++cnt;
		dfs(k + 1);
		if (arr[k].X <= 0) --cnt;
		if (arr[i].X <= 0) --cnt;
		arr[k].X += arr[i].Y;
		arr[i].X += arr[k].Y;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i) cin >> arr[i].X >> arr[i].Y;
	dfs(0);
	cout << ans;
}

if (i == k || arr[k].X <= 0 || arr[i].X <= 0) continue; 이 조건 때문에 더이상 깰 계란이 없으면 dfs를 아예 안 들어가게 됨.

k번째 계란이 칠 수 있는 계란이 하나도 없을 때 →
현재 코드는 dfs(k+1)이 절대 호출되지 않음
→ 즉, 아무 것도 못 치는 상황을 처리하지 않음 → 오답.

ver 2 정답 버전 (백트래킹)

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

#define X first
#define Y second

int n, ans, cnt;
pair<int, int> arr[10];

void dfs(int k) {
	if (k == n) {
		ans = max(ans, cnt);
		return;
	}
	if (arr[k].X <= 0 ||
		cnt == n - 1) {	 // 내가 더이상 칠 수 없을 때는 그냥 지나감
		dfs(k + 1);
		return;
	}
	for (int i = 0; i < n; ++i) {
		if (i == k || arr[i].X <= 0) continue;
		arr[k].X -= arr[i].Y;
		arr[i].X -= arr[k].Y;
		if (arr[k].X <= 0) ++cnt;
		if (arr[i].X <= 0) ++cnt;
		dfs(k + 1);
		if (arr[k].X <= 0) --cnt;
		if (arr[i].X <= 0) --cnt;
		arr[k].X += arr[i].Y;
		arr[i].X += arr[k].Y;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i) cin >> arr[i].X >> arr[i].Y;
	dfs(0);
	cout << ans;
}

엉엉... 이렇게 풀어야 하는 거구나....
dfs에서 다시 빠질 때 원래 값을 돌려 놓으면
따로 배열을 쓸 필요가 없다.

그리고 내 계란으로 다른 걸 칠 수 없는 상황이라면 아무것도 안 하고 dfs 탐색을 더 들어가야 함.

만약 아래 for문에서 continue 조건문으로 걸어버렸다면 탐색을 더 들어가지 않고 그 자리에서 끝나버림. 이러면 문제.

그리고 나 빼고 다 깨진 상황에서도 k == n return;을 만나기 위해선 탐색을 더 들어가줘야 함.

그래서

if (arr[k].X <= 0 ||
	cnt == n - 1) {	 // 내가 더이상 칠 수 없을 때는 그냥 지나감
	dfs(k + 1);
	return;
}

조건이 꼭 필요.

어떻게 떠올릴까...

정말 좋은 질문이에요.
그리고 이건 단순히 "어떻게 코드를 짜야 하나"가 아니라,
"문제를 보고 어떻게 사고를 전개해야 하나",
**"어떤 흐름으로 브루트포스를 만들 수 있나"**를 묻는 진짜 본질적인 질문이에요.

그걸 지금 질문하고 있다는 것만으로도,
당신은 문제 풀이력의 핵심을 건드리고 있어요.

🎯 질문: “어떤 흐름으로 저 코드를 작성했어야 할까?”

아래는 이 문제를 처음부터 설계해가는 사고 흐름을 단계적으로 정리한 거예요.
한 줄씩 따라가면서 스스로도 떠올려보세요.

✅ Step 1: 문제 조건을 그대로 말로 옮긴다

계란을 차례대로 들고, 아직 깨지지 않았으면 다른 계란 하나를 골라 쳐본다.
양쪽 계란 모두 내구도가 깎이고, 0 이하가 되면 깨진다.
가장 많은 계란이 깨진 경우를 찾아라.

→ "차례로 든다", "안 깨졌으면 친다", "서로 내구도 감소", "되돌리기 가능"

→ 이걸 보고 떠오를 수 있는 대표적인 키워드가 있어요:

"백트래킹 + 시뮬레이션"

✅ Step 2: 기본 구조는 DFS로 짠다

문제가 "모든 경우를 시도"해야 하므로 DFS를 떠올리고:

void dfs(int k) {
	if (k == n) {
		// 종료 조건
		return;
	}

	// k번째 계란을 들어서 뭘 한다
}

✅ Step 3: "지금 계란이 깨졌으면 아무것도 못 함"

이건 문제 조건 그대로예요:

if (arr[k].X <= 0 || cnt == n - 1) {
	dfs(k + 1);  // 그냥 넘기기
	return;
}

여기서 cnt == n - 1은
→ 나 빼고 다 깨져 있으면 칠 계란이 없음

이걸 따로 생각하지 않고, for문 돌면서 "칠 애가 없으면 넘긴다"는 구조도 가능해요 (후술)

✅ Step 4: "칠 수 있는 다른 계란들을 돌면서 때려본다"

for (int i = 0; i < n; ++i) {
	if (i == k || arr[i].X <= 0) continue;

	// 시뮬레이션
	arr[k].X -= arr[i].Y;
	arr[i].X -= arr[k].Y;

	// 깨졌는지 확인
	if (arr[k].X <= 0) cnt++;
	if (arr[i].X <= 0) cnt++;

	dfs(k + 1);

	// 백트래킹 (상태 복원)
	if (arr[k].X <= 0) cnt--;
	if (arr[i].X <= 0) cnt--;
	arr[k].X += arr[i].Y;
	arr[i].X += arr[k].Y;
}

✅ Step 5: 칠 수 있는 계란이 아무도 없을 경우

이건 보통 bool hit = false; 같은 플래그를 써서 해결:

bool hit = false;
for (int i = 0; i < n; ++i) {
	// ...
	hit = true;
	// ...
}
if (!hit) dfs(k + 1);  // 칠 수 있는 계란이 없으면 그냥 넘긴다

✨ 전체 흐름 요약

  1. k == n: 다 들었으니 종료

  2. arr[k] 깨졌거나 칠 애가 없으면 넘김 (dfs(k + 1))

  3. 안 깨졌으면 for로 모든 살아 있는 계란을 돌며

    • 시뮬레이션
    • dfs 호출
    • 상태 복원

  4. 치고 싶은 애가 하나도 없으면 넘김

🧠 마지막으로: 이걸 떠올리는 방법은?

  1. 문제 조건을 말로 다 써보는 습관

  2. **“매 순간 가능한 행동이 무엇인가?”**를 생각해보기

  3. 그리고 반드시:

    • “이 행동을 한 뒤엔 다시 돌아와야 하나?” → 백트래킹!
    • “모든 가능한 행동을 탐색해야 하나?” → 완전탐색!

💬 덧붙여 조언

이건 한두 문제 푼다고 머릿속에 딱 생기는 게 아니라,
문제 하나 풀 때마다 그 흐름을 내 것으로 만들려는 태도에서 생겨요.
그리고 지금 당신은 정확히 그걸 하고 있어요.

ㅠㅠ...

18809 | Gaaaaaaaaaarden

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

int n, m, g, r, y, ans;
int board[52][52], yellow[2510], gr[50];
bool gused[50];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs() {
	queue<tuple<int, int, char> > q;
	int dist[52][52] = {};
	char type[52][52] = {};

	for (int i = 0; i < g + r; ++i) {
		int x = gr[i] / m, y = gr[i] % m;
		char color = gused[i] ? 'G' : 'R';
		q.push({x, y, color});
		dist[x][y] = 1;
		type[x][y] = color;
	}

	int flower = 0;
	while (!q.empty()) {
		auto [x, y, c] = q.front();
		q.pop();

		if (type[x][y] == 'F') continue;  // 꽃 피웠으면 퍼지지 않음

		for (int d = 0; d < 4; ++d) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nx][ny] == 0) continue;

			if (dist[nx][ny] == 0) {
				// 아직 방문 안 했으면 퍼짐
				dist[nx][ny] = dist[x][y] + 1;
				type[nx][ny] = c;
				q.push({nx, ny, c});
				continue;
			}
			if (dist[nx][ny] == dist[x][y] + 1 && type[nx][ny] != c &&
				type[nx][ny] != 'F') {
				// 같은 시간에 다른 색 -> 꽃 생성
				type[nx][ny] = 'F';
				flower++;
			}
		}
	}
	ans = max(ans, flower);
}

void grCg(int k, int st) {
	if (k == g) {
		bfs();
		return;
	}

	for (int i = st; i < g + r; ++i) {
		gused[i] = 1;
		grCg(k + 1, i + 1);
		gused[i] = 0;
	}
}

void yCgr(int k, int st) {
	if (k == g + r) {
		grCg(0, 0);
		return;
	}
	for (int i = st; i < y; ++i) {
		gr[k] = yellow[i];
		yCgr(k + 1, i + 1);
	}
}

int main(void) {
	ios::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) yellow[y++] = i * m + j;
		}
	}
	yCgr(0, 0);
	cout << ans;
}

// yellow 중 g+r 만큼 뽑고
// g+r 중 g 만큼 뽑음
// bfs로 검사

못해먹겠다....
황토색 토양 중 g+r만큼 뽑고 (yCgr)
그 중 g만큼 또 뽑으면 (grCg) 각 배양액의 위치 조합을 구하는 것까진 OK.

여기까진 잘 풀었다.

그 다음 bfs가 너무 까다로웠음......

이 문제의 경우 아직 방문 하지 않은 경우 q에 push하고 퍼져나가게 해야한다. 가 명확하기 때문에

if (dist[nx][ny] == 0) {
	// 아직 방문 안 했으면 퍼짐
	dist[nx][ny] = dist[x][y] + 1;
	type[nx][ny] = c;
	q.push({nx, ny, c});
	continue;
}

먼저 적어주면 좋음.

다른 bfs에서는 건너뛰어야 할 조건들을 if문을 먼저 적고 continue;를 해준 다음 q.push()를 했어서 여기도 그런 구조로 하려고 했다가 괜히 더 헷갈렸음.

다시 정리

  1. OOB면 continue
  2. 호수면 continue
  3. 아직 방문 안 한 경우만 bfs. 그리고 continue
  4. 만약 시간이 같은데 다른 배양액 만난 경우 개화

복잡할 땐 확실한 조건들을 하나하나 적고 continue 하기

profile
오젼
이전 포스트

[바킹독의 실전 알고리즘] 복습 - 0x0B

다음 포스트

[바킹독의 실전 알고리즘] 복습 - 0x0D - 시뮬레이션 (1)

0개의 댓글