글 읽기 - 벡트래킹, BFS 사용하여 풀었는데 해당 로직이 맞는 지 모르겠습니다.

cgin1202 4년 전 0

다른 사람들의 코드와 조금은 다르지만 로직은 비슷하다고 생각합니다.

1. RED, GREEN 넣을 수 있는 위치 중에서 RED, GREEN 개수만큼 조합을 돌려서 구합니다.

2.1번에서 구한 것에서 RED의 개수만큼 다시 조합을 돌려서 구합니다.

3. 2번에서 구한 것에서 BFS를 사용하여 풉니다.

3-1. 초록색이 먼저 이동합니다.

3-2. 동일 시간대에 초록이 이동한 칸을 기억해내고 다음에 빨간색칸이 이동하게 합니다.

3-3. 빨간색이 이번에 이동할 때, 이미 방문을 하였다면 초록색칸이 이동을 하였던 칸인지 확인을 합니다. 해당칸은 FLOWER 처리합니다.

3-4. 이러한 방식을 초록색과 빨간색이 더 이상 이동할 수 없을 때까지 BFS를 돌렸습니다.

*제 생각이지만, 3-1~3-3 에서 로직에서 틀렸다고 생각합니다.*

*벡트래킹에서는 직접 확인해보았을 때 문제가 없었습니다.*

*궁금한 점은 3-1~3-3 같은 로직으로 해당문제를 풀어나가도 되는 지 궁금합니다;*

*추가적으로 해당 코드는 제출 후 78퍼에서 틀리고 있습니다..*

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>

using namespace std;

int n, m;
int board[51][51];
vector<pair<int, int>> possibleBoard;
int r, g;
bool possiblevisited[11];
int possibleSize = 0;
vector<int> indexRedGreen;
queue<pair<int, int>> red;
queue<pair<int, int>> green;
bool redvisited[11];
int maxValueLength = 0;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
bool bfsvisited[51][51];
int tempBoard[51][51];
int flowerlength = 0;


// red, green 한 칸 씩 이동하는 함수
//숫자 0 : 호수 , 숫자 5 : flower

void bfs() {

	vector<pair<int, int>> tempStore;

	int greenSize = green.size();
	for (int i = 0; i < greenSize; i++) {
		int x = green.front().first;
		int y = green.front().second;
		green.pop();
		if (tempBoard[x][y] == 5)	// flower 넘어가기
			continue;
		for (int k = 0; k < 4; k++) {
			int nextdx = x + dx[k];
			int nextdy = y + dy[k];
			if (nextdx >= 0 && nextdy >= 0 && nextdx < n && nextdy < m) {
				if (bfsvisited[nextdx][nextdy] == true)
					continue;
				if (tempBoard[nextdx][nextdy] == 0)
					continue;

				if (tempBoard[nextdx][nextdy] == 5)
					continue;

				bfsvisited[nextdx][nextdy] = true;
				green.push({ nextdx, nextdy });
				tempStore.push_back({ nextdx, nextdy });
			}
		}
	}


	int redSize = red.size();
	int tempSize = tempStore.size();

	for (int i = 0; i < redSize; i++) {
		int x = red.front().first;
		int y = red.front().second;
		red.pop();
		if (tempBoard[x][y] == 5)
			continue;
		for (int k = 0; k < 4; k++) {
			int nextdx = x + dx[k];
			int nextdy = y + dy[k];
			
			if (tempBoard[nextdx][nextdy] == 5)
				continue;
			if (nextdx >= 0 && nextdy >= 0 && nextdx < n && nextdy < m) {
				if (tempBoard[nextdx][nextdy] == 0)
					continue;
				bool flowercheck = false;

				if (bfsvisited[nextdx][nextdy] == true) {
					for (int tk = 0; tk < tempSize; tk++) {
						int comparex = tempStore[tk].first;
						int comparey = tempStore[tk].second;
						if (nextdx == comparex && nextdy == comparey) {
							tempBoard[nextdx][nextdy] = 5;
							flowercheck = true;
							break;
						}
					}

					if (flowercheck == true)
						flowerlength++;
				}
				else {
					if (tempBoard[nextdx][nextdy] == 5)
						continue;

					bfsvisited[nextdx][nextdy] = true;
					red.push({ nextdx, nextdy });
				}

			}
		}
	}

	
}

// green, red 빌 때까지 돌리기

void playgame() {
	flowerlength = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			bfsvisited[i][j] = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			tempBoard[i][j] = board[i][j];


	while (1) {
		if (green.size() == 0 && red.size() == 0)
			break;
		bfs();
	}
	maxValueLength = max(maxValueLength, flowerlength);
}


// red, green 경우의 수 구하기

void selectRed(int idx, int length) {
	if (length == r) {
		for (int i = 0; i < r + g; i++) {
			int boardindex = indexRedGreen[i];
			if (redvisited[i] == true) {
				red.push({ possibleBoard[boardindex].first, possibleBoard[boardindex].second });
			}
			else {
				green.push({ possibleBoard[boardindex].first, possibleBoard[boardindex].second });
			}
		}
		playgame();
		//cnt++;
		return;
	}

	for (int i = idx; i < r + g; i++) {
		if (redvisited[i] == true)
			continue;
		redvisited[i] = true;
		selectRed(i, length + 1);
		redvisited[i] = false;
	}
}

// 가능한 지역 구하기

void selectPossibleGround(int idx, int length) {
	if (length == r + g) {
		indexRedGreen.clear();
		for (int i = 0; i < possibleSize; i++) {
			if (possiblevisited[i] == true) {
				indexRedGreen.push_back(i);
			}
		}
		selectRed(0, 0);

		return;
	}
	
	for (int i = idx; i < possibleSize; i++) {
		if (possiblevisited[i] == true)
			continue;
		possiblevisited[i] = true;
		selectPossibleGround(i, length + 1);
		possiblevisited[i] = false;
	}
}

// 초기화

void init() {
	cin >> n >> m;
	cin >> r >> g;
	for(int i=0; i<n; i++)
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				possibleBoard.push_back({ i,j });
			}
		}

}

// main

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	init();
	possibleSize = possibleBoard.size();
	selectPossibleGround(0, 0);
	//cout << cnt << "\n";
	cout << maxValueLength << "\n";
	return 0;
}

cgin1202 4년 전 0

해당 문제 초기에 red, green 경우의 수 확인하고 bfs 돌리기전에 visited = true 로 하니 해결되었습니다! 이런 실수를 하다니ㅠ

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

문제

문제

출처

ICPC

벡트래킹, BFS 사용하여 풀었는데 해당 로직이 맞는 지 모르겠습니다.

cgin1202 4년 전 0

cgin1202 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말