글 읽기 - 14502(연구소) next_permutation 1번만 도는 이유를 모르겠습니다

jhim000 4년 전 0

제가 접근한 방식은 공백 위치를 empty_place라는 deque에 담고, 그 크기만큼 permutation이라는 int형 배열을 만들어서 permutation[0] = 1; permutation[1] = 1; permutation[2] = 1; 이렇게 할당하고, 나머지는 전부 0으로 할당했습니다. 그 후 do~while(next_permutation(permutation, permutation+zero_cnt)) 문으로 1의 위치를 바뀌게 하여 조합을 해결하려 했는데, 결과적으로 총 35C3번 do~while문이 돌아가야 하는데, 저는 한번만 돌아갑니다.

알려주시면 감사하겠습니다ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
struct virus {
	int y, x;
};
// 0: 빈칸, 1: 벽, 2: 바이러스
// 2 <= 바이러스(2)의 개수 <= 10
// 빈칸 (0)의 개수는 3개 이상
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int N, M;
int map[8][8], map2[8][8];
int result = -1;
//int permutation_cnt = 0;
deque<virus> v, v2;
deque<virus> empty_place;
int main(void) {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				v.push_back({ i, j }); // 바이러스 위치 담기
				v2.push_back({ i, j }); // 임시용
			}
			if (map[i][j] == 0)	empty_place.push_back({ i, j }); // 공백 위치 담기
			map2[i][j] = map[i][j];
			
		}
	}

	// map의 0 부분이 몇개인지 추출해서 그 부분에 1을 넣을 수 있는 경우에 대해 brute force
	int zero_cnt = empty_place.size(); // 공백인 자리 전체 개수
	int *permutation = new int[zero_cnt];
	for (int i = 0; i < zero_cnt; i++)	permutation[i] = 0;
	permutation[0] = 1; permutation[1] = 1; permutation[2] = 1;
	// 그럼 permutation 배열과 empty_place 벡터의 사이즈는 같고, 맞게 벽(1)을 배치하면 된다.
	do {
		//permutation_cnt++;
		// do~while 문 돌릴 때 마다 virus 위치와 맵 정보 초기화
		for (int i = 0; i < v2.size(); i++)	v[i] = v2[i];
		for (int i = 0; i < N; i++)	for (int j = 0; j < M; j++)	map[i][j] = map2[i][j];

		for (int i = 0; i < zero_cnt; i++) {
			if (permutation[i] == 1) map[empty_place.at(i).y][empty_place.at(i).x] = 1;
		}

		while (!v.empty()) {
			virus tmp = v.front(); v.pop_front();
			for (int i = 0; i < 4; i++) {
				int y = tmp.y + dy[i];
				int x = tmp.x + dx[i];

				if (y < 0 || y >= N || x < 0 || x >= M)	continue;
				if (map[y][x] == 0) {
					map[y][x] = 2;
					v.push_back({ y, x });
				}
			}
		}

		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)	count++;
			}
		}

		result = max(result, count);
	} while (next_permutation(permutation, permutation + zero_cnt));
	// 현재 next_permutation이 작동하지 않음
	//cout << permutation_cnt << endl;
	cout << result;

	return 0;
}

djm03178 4년 전 1

1 1 1 0 0 0 0 ...은 사전순으로 가장 마지막의 모습이기 때문에 여기서 next_permutation이 호출되면 false가 반환됩니다.

jhim000 4년 전 0

감사합니다. 그 부분은 0 0 0 0 0 0 0 1 1 1로 바꿔주니 해결되었습니다!

근데 여전히 프로그램 작동 로직은 맞다고 생각하는데 정답은 안나옵니다..

이런 경우에는 어떻게 해결해나갈까요.. ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
struct virus {
	int y, x;
};
// 0: 빈칸, 1: 벽, 2: 바이러스
// 2 <= 바이러스(2)의 개수 <= 10
// 빈칸 (0)의 개수는 3개 이상
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int N, M;
int map[8][8], map2[8][8];
int result = -1;
deque<virus> v, v2;
deque<virus> empty_place;
int main(void) {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			map2[i][j] = map[i][j];
			if (map[i][j] == 2) {
				v.push_back({ i, j }); // 바이러스 위치 담기
				v2.push_back({ i, j }); // 임시용
			}
			if (map[i][j] == 0)	empty_place.push_back({ i, j }); // 공백 위치 담기
		}
	}

	// map의 0 부분이 몇개인지 추출해서 그 부분에 1을 넣을 수 있는 경우에 대해 brute force
	int zero_cnt = empty_place.size(); // 공백인 자리 전체 개수
	int *permutation = new int[zero_cnt];
	for (int i = 0; i < zero_cnt - 3; i++)	permutation[i] = 0;
	for (int i = zero_cnt - 3; i < zero_cnt; i++)	permutation[i] = 1;

	// 그럼 permutation 배열과 empty_place 벡터의 사이즈는 같고, 맞게 벽(1)을 배치하면 된다.
	do {
		// do~while 문 돌릴 때 마다 virus 위치와 맵 정보 초기화
		for (int i = 0; i < v2.size(); i++)	v[i] = v2[i];
		for (int i = 0; i < N; i++)	for (int j = 0; j < M; j++)	map[i][j] = map2[i][j];
		for (int i = 0; i < empty_place.size(); i++) {
			if (permutation[i] == 1) 
				map[empty_place.at(i).y][empty_place.at(i).x] = 1;
		}

		while (!v.empty()) {
			virus tmp = v.front(); v.pop_front();
			for (int i = 0; i < 4; i++) {
				int y = tmp.y + dy[i];
				int x = tmp.x + dx[i];
				
				if (y < 0 || y >= N || x < 0 || x >= M)	continue;
				if (map[y][x] == 0) {
					map[y][x] = 2;
					v.push_back({ y, x });
				}
			}
		}

		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) count++;
			}
		}

		result = max(result, count);
	} while (next_permutation(permutation, permutation + zero_cnt));
	cout << result;

	return 0;
}

djm03178 4년 전 1

한 번 루프를 돌 때마다 v의 모든 원소를 다 pop했기 때문에 v의 크기는 0이 되고, 그래서 43번째 줄처럼 단순히 인덱스로 접근하면 안 됩니다. 다시 push_back을 해줘야 합니다.

jhim000 4년 전 0

감사합니다ㅠ

그 문제 때문인줄은 몰랐습니다..

전에도 계속 안됬는데, 이 문제였네요;;

마지막에 for 문으로 v에 push 하니깐 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14502(연구소) next_permutation 1번만 도는 이유를 모르겠습니다

jhim000 4년 전 0

djm03178 4년 전 1

jhim000 4년 전 0

djm03178 4년 전 1

jhim000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말