대엉코딩

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

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

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

	return 0;
}

** 잘못된 내용이 있으면 알려주세요 **

www.acmicpc.net/problem/17142

1. 풀이방법

- 브루트포스(경우의 수 모두 구하기) + BFS탐색 (바이러스 전파) 문제입니다.

- 전 빈칸의 개수를 입력받을 때 미리 구해놓고 종료조건으로 활용하였습니다.

2. 주의사항

- 종료조건을 큐 가 비었을 때만 걸면 안됩니다. 빈칸은 없지만 비활성바이러스만 남아있을경우 BFS를 또 돌게되어

- 출력이 달라집니다.

- 그래서 종료조건에 빈칸이 모두 없어졌을 때를 추가로 걸어주었습니다.

- 제한시간이 0.25초 인데 만약 모두 전이되었는지 체크를 할때 이중탐색문을 사용할 경우 시간초과가 뜰 수 있습니다.

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;

int n, m;
int vground[51][51];
bool visit[51][51];
int minresult = 9999;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
vector<pair<int, int>> canvirus;
vector<pair<int, int>> tmpvirus;
queue<pair<int, int>> tmpq;
bool suc = false;
int totalzero = 0;
int tmpzero = 0;


void inputs() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) { //0은 빈칸, 1은 벽, 2는 바이러스 가능위치
		for (int j = 0; j < n; j++) {
			cin >> vground[i][j];
			if (vground[i][j] == 2) {
				canvirus.push_back({ i,j });
			}
			if (vground[i][j] == 0) {
				totalzero++;
			}
		}
	}
}
void qclear() {
	while (!tmpq.empty()) {
		tmpq.pop();
	}
}
void vtoq() {
	for (int i = 0; i < tmpvirus.size(); i++) {
		tmpq.push(tmpvirus[i]);
		visit[tmpvirus[i].first][tmpvirus[i].second] = true;
	}
}
void visitclear() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = false;
		}
	}
}
bool boundcheck(int x, int y) {
	if (x < 0 || x >= n || y < 0 || y >= n) return false;
	else return true;
}

void bfs() {
	int second=0;
	while (1) {
		if (tmpzero==0|| tmpq.empty()) break;
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (boundcheck(tx, ty) && visit[tx][ty] == false && vground[tx][ty]!=1) {
					tmpq.push({ tx,ty });
					visit[tx][ty] = true;
					if (vground[tx][ty] == 0) tmpzero--;
				}
			}
		}
		second++;
	}
	if (tmpzero==0) {
		suc = true;
		if (second < minresult) minresult = second;
	}

}

void makecase(int index,int cnt) {
	if (cnt == m) {
		visitclear(); //방문배열 초기화
		qclear(); //큐 를 먼저 싹 빼줌 초기화
		vtoq(); //벡터에서 큐로 옮기기 (방문체크도)
		tmpzero = totalzero; // 바이러스가 모두 전파되었는지확인
		bfs();
		return;
	}
	for (int i = index; i < canvirus.size(); i++) {
		tmpvirus.push_back(canvirus[i]);
		makecase(i + 1, cnt + 1);
		tmpvirus.pop_back();
	}

}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	makecase(0,0);
	if (suc == true) cout << minresult << "\n";
	else cout << -1 << "\n";
	return 0;
}

www.acmicpc.net/problem/2422

1. 풀이방법 

- 1~N까지의 모든 아이스크림 중 3개를 만드는 모든 조합을 골라서

- 이게 가능한지 (최악의 조합에 속하는 것이 없는 지) 를 확인 후 방법의 수를 증가시켜 주면되는 문제였습니다.

- 조합을 만드는 것은 어렵지 않았고, 처음에는 최악의 조합을 <pair<int,int>>로 만들어

- 반복문을 통해서 psice() 가능한 아이스크림조합인지를 확인 했었는데, 시간초과가 발생하였습니다.

- 반복문 탐색 중 정지 조건 break 를 걸어 주고 난 뒤 제출해도 역시 시간초과 였습니다.

- 그래서 이차원배열을 선언하여 두 아이스크림이 최악의 조합인지를 O(1) 시간에 확인할 수 있도록

- 수정하여 제출 하였더니 통과 되었습니다.

- 그래프 구현방법 중 인접행렬 방식( 두 노드가 인접했는지 확인하는 것이 매우 빠르다라는 장점)

- 으로 부터 나온 생각으로 구현하였습니다.

2. 주의사항

- 문제 자체는 쉬웠지만, 시간을 단축하는 부분에 있어 특이점이 있는 것 같아 포스팅으로 남깁니다.

3. 나의코드 

- 주석 부분은 반복문을 통한 탐색 부 입니다.

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

int N;
int M;
int t1, t2;
// vector<pair<int, int>> worstice;
bool wi[201][201];
vector<int> icearr;
int pscase = 0;

/*bool psice() {
	for (int i = 0; i < worstice.size(); i++) {
		int tmp = 0;
		for (int j = 0; j < icearr.size(); j++) {
			if (icearr[j] == worstice[i].first || icearr[j] == worstice[i].second) {
				tmp++;
			}
			if (tmp == 2) return false;
			if (icearr[j] > worstice[i].second) break;
		}
	}
	return true;
}*/
bool ps() {
	if (wi[icearr[0]][icearr[1]] == true || wi[icearr[0]][icearr[2]] == true
		|| wi[icearr[1]][icearr[2]] == true) return false;
	else return true;
}

void makeice(int index,int cnt) {
	if (cnt == 3) {
		if (ps()) {
			pscase++;
		}
		return;
	}
	for (int i = index; i <= N; i++) {
		icearr.push_back(i);
		makeice(i+1,cnt + 1);
		icearr.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2;
		// worstcase.push_back({t1,t2});
		wi[t1][t2] = true;
		wi[t2][t1] = true;
	}
	makeice(1,0);

	cout << pscase << "\n";

	return 0;
}