글 읽기 - 조합이 잘못된 걸까요?

soph456 5년 전 0

vc 벡터에 가능한 조합의 경우의 수를 다 넣고

조합의 경우에 따라 bfs 로 결과를 찾습니다.

틀렸습니다에 결국 다시 엎고 다른걸로 통과는 했지만

아래 코드가 어떤 부분이 잘못되어 통과하지 못하는지 궁금합니다.

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

int N, M;
int ans = 0;
int board[8][8];
int tboard[8][8];

vector<vector<int> > vc; //모든 조합들이 담기는 곳
vector<int> ary;

queue<pair<int, int> > tq;

void dfs(int start, int cnt) {
	if (ary.size() == 3) {
		vc.push_back(ary);
		return;
	}

	int mm = (N - 1)*M + (M - 1);
	for (int i = start; i < mm; i++) {
		if (cnt == 0 || ary.back() < i) {
			if (board[i / M][i%M] == 0) {
				ary.push_back(i);
				dfs(cnt + 1, i + 1);
				ary.pop_back();
			}
		}
	}
}

bool outRange(int i, int j) { //범위를 벗어나면 true를 반환
	if (0 <= i && i < N && 0 <= j && j < M) {
		return false;
	}
	return true;
}

void problem() {
	copy(&board[0][0], &board[0][0] + 8 * 8, &tboard[0][0]);
	
    //각 조합에 따라 bfs로 퍼진다.
	//이때의 최고값을 정한다.
	int di[4] = { -1,1,0,0 };
	int dj[4] = { 0,0,-1,1 };
	queue<pair <int, int> > q = tq;

	while (!q.empty()) {
		pair<int, int> vi = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ii = vi.first + di[i];
			int jj = vi.second + dj[i];

			if (!outRange(ii, jj) && tboard[ii][jj] == 0) {
				tboard[ii][jj] = 2;
				q.push(make_pair(ii, jj));
			}

		}
	}
    
    //안전공간의 수 탐색
	int t = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tboard[i][j] == 0) {
				t++;
			}
		}
	}
	ans = max(t, ans);

}

int main() {

	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
			tboard[i][j] = board[i][j];

			if (board[i][j] == 2) {
				tq.push(make_pair(i, j));
			}
		}
	}

	//1.
	// 벽의 조합을 구한다. (3)
	// 순서는 상관없지만, 조합들이 중복되서는 안된다.
	// 벽의 위치는 i*M+j 로 한다.
	dfs(0, 0);

	int i; int j;
	for (int k = 0; k < vc.size(); k++) {
		for (auto p : vc.at(k)) {
			i = p / M; j = p % M;
			board[i][j] = 1;
		}
		problem();
		for (auto p : vc.at(k)) {
			i = p / M; j = p % M;
			board[i][j] = 0;
		}
	}

	printf("%d", ans);
	return 0;
}

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

문제

문제

출처

ICPC

조합이 잘못된 걸까요?

soph456 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말