[순열, 조합] 기본 코드 및 예제 문제: 암호 만들기, 소문난 칠공주_백준

순열

n P r

int N, R;

void permutation(vector<int>& vec, vector<bool>& visited, int depth) {
	// 종료 조건
	if (depth == R) {
		for (int i = 0; i < vec.size(); i++) {
			cout << vec[i]+1 << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < N; i++) {
		if (visited[i])
			continue;
		vec.push_back(i);
		visited[i] = true;
		permutation(vec, visited, depth + 1);
		// 복구
		visited[i] = false;
		vec.pop_back();
	}
}				

// 5P3 순열
1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2

중복 순열

									// visited 사용x
void duplicatePermutation(vector<int>& vec, int depth) {
	// 종료 조건
	if (depth == R) {
		for (int i = 0; i < vec.size(); i++) {
			cout << vec[i]+1 << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < N; i++) {
		vec.push_back(i);
		//permutation(vec, i + 1, depth + 1);
		duplicatePermutation(vec, depth + 1);	// 일반 순열과의 차이점
		// 복구
		vec.pop_back();
	}
}

5P3 중복 순열
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
1 2 2
1 2 3
1 2 4
1 3 1
1 3 2
1 3 3
1 3 4
1 4 1
1 4 2
1 4 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4
2 2 1
2 2 2
2 2 3
2 2 4
2 3 1
2 3 2
2 3 3
2 3 4
2 4 1
2 4 2
2 4 3
2 4 4
3 1 1
3 1 2
3 1 3
3 1 4
3 2 1
3 2 2
3 2 3
3 2 4
3 3 1
3 3 2
3 3 3
3 3 4
3 4 1
3 4 2
3 4 3
3 4 4
4 1 1
4 1 2
4 1 3
4 1 4
4 2 1
4 2 2
4 2 3
4 2 4
4 3 1
4 3 2
4 3 3
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4

조합

n C r

void combination(vector<int>& vec, int startIdx, int depth) {
	// 종료 조건
	if (depth == R) {
		for (int i = 0; i < vec.size(); i++) {
			cout << vec[i]+1 << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = startIdx; i < N; i++) {
		vec.push_back(i);
		combination(vec, i + 1, depth + 1);
		// 복구
		vec.pop_back();
	}
}

// 4C3 조합
1 2 3
1 2 4
1 3 4
2 3 4

중복 조합

void nonDuplicateCombination(int prevIdx, const vector<int>& inputVec, vector<int>& vec, int startIdx, int depth) {
	// 종료 조건
	if (depth == R) {
		for (int i = 0; i < R; i++) {
			cout << inputVec[vec[i]] << ' ';
		}
		cout << '\n';
		return;
	}

	//int prevIdx = startIdx-1;	// 중복 방지용 
	for (int i = startIdx; i < inputVec.size(); i++) {
		if (prevIdx != -1 && inputVec[prevIdx] == inputVec[i])
			continue;

		vec.push_back(i);
		nonDuplicateCombination(i, inputVec, vec, i + 1, depth + 1);
		// 복구
		vec.pop_back();

		// prev 갱신
		prevIdx = i;
	}
}

// 4C3 중복조합
1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
2 2 2
2 2 3
2 2 4
2 3 3
2 3 4
2 4 4
3 3 3
3 3 4
3 4 4
4 4 4

---

예제 문제1: 암호 만들기_백준

source: https://www.acmicpc.net/problem/1759

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

string Con = "bcdfghjklmnpqrstvwxyz";
unordered_set<char> us_con;

int L, C;

// O(nCl)
void alphabetCombination(vector<char>& temp, const vector<char>& S, int startIdx, int depth, int numOfCon, int numOfVow) {
	// 종료 조건
	if (depth == L) {
		// 암호 조건 체크
		if (numOfCon < 2)
			return;
		if (numOfVow < 1)
			return;

		for (int i = 0; i < L; i++) {
			cout << temp[i];
		}
		cout << '\n';
		return;
	}

	// 탐색
	for (int i = startIdx; i < S.size(); i++) {
		char c = S[i];
        // 암호문 조건 체크를 위해 자음 갯수, 모음 갯수를 카운팅 
		// c가 자음인 경우
		if (us_con.find(c) != us_con.end()) {
			temp[depth] = S[i];
			alphabetCombination(temp, S, i + 1, depth + 1, numOfCon+1, numOfVow);
		}
		// c가 모음인 경우
		else {
			temp[depth] = S[i];
			alphabetCombination(temp, S, i + 1, depth + 1, numOfCon, numOfVow + 1);
		}
	}
}

void solution(vector<char>& S) {
	// (1) 문자들을 정렬한다.
	sort(S.begin(), S.end());

	// (2) c C l 의 조합을 찾는다. 
	// 이미 정렬이 되어있으므로 조합으로 찾으면 자연스레 조합도 정렬된다. 
	vector<char> temp(L);
	alphabetCombination(temp, S, 0, 0, 0, 0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 자음 us 만들기
	for (int i = 0; i < Con.size(); i++) {
		us_con.insert(Con[i]);
	}


	cin >> L >> C;
	vector<char> S(C);
	for (int i = 0; i < C; i++) {
		cin >> S[i];
	}

	solution(S);

	return 0;
}

---

예제 문제2: 소문난 칠공주_백준

source: https://www.acmicpc.net/problem/1941

1. 총 25명의 학생 중에서, 7명을 뽑기, 25C7: int combination25C7(vector<pair<int, int>>& temp, int startIdx, int depth)
2. (조건1) 하나의 조합에서 이다솜파 학생이 적어도 4명 이상 있는지 확인: bool checkSomNum(const vector<pair<int, int>>& group)
3. (조건2) 하나의 조합에서 그 7명이 서로 인접해 있는지 확인: bool checkNeighbor(const vector<pair<int, int>>& group)

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

vector<string> MAP(5);
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

bool checkSomNum(const vector<pair<int, int>>& group) {
	int cntOfSom = 0;
	for (int i = 0; i < 7; i++) {
		if (MAP[group[i].first][group[i].second] == 'S')
			cntOfSom++;
	}

	if (cntOfSom < 4)
		return false;
	else
		return true;
}

int bfsCheck(const vector<pair<int, int>>& group, vector<vector<bool>>& visited, int x, int y) {
	
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = false;
	int neighborSize = 1;

	while (!q.empty()) {
		pair<int, int> nowLoc = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = nowLoc.first + dx[i];
			int ny = nowLoc.second + dy[i];

			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5)
				continue;
			if (visited[nx][ny] == false)
				continue;

			neighborSize++;
			visited[nx][ny] = false;
			q.push({ nx, ny });
		}
	}

	return neighborSize;
}

bool checkNeighbor(const vector<pair<int, int>>& group) {
	vector<vector<bool>> visited(5, vector<bool>(5, false));
	for (int i = 0; i < 7; i++) {
		visited[group[i].first][group[i].second] = true; // 멤버 존재
	}
	
	int neighbor = bfsCheck(group, visited, group[0].first, group[0].second);

	if (neighbor != 7)
		return false;
	else
		return true;
}

int combination25C7(vector<pair<int, int>>& temp, int startIdx, int depth) {
	// 종료 조건
	if (depth == 7) {
			return 0;
		if (!checkNeighbor(temp))
			return 0;
		
		return 1;
	}

	int cnt = 0;
	for (int i = startIdx; i < 25; i++) {
		int x = i % 5;
		int y = i / 5;

		temp[depth] = { x, y };
		cnt += combination25C7(temp, i + 1, depth + 1);
	}

	return cnt;
}

int solution() {
	// 25C7의 조합을 구한다.
	vector<pair<int, int>> temp(7);
	int answer = combination25C7(temp, 0, 0);
	return answer;
}

int main() {
	for (int i = 0; i < 5; i++) {
		string s;
		cin >> s;
		MAP[i] = s;
	}

	int answer = solution();
	cout << answer << '\n';

	return 0;
}