글 읽기 - 정말 어렵네요;; 4프로 뚫으니까 12?프로에서 막힙니다 ㅠ

yth1130 6년 전 0

12프로정도에서 틀렸습니다 가 나오는데

일단 질문게시판에 있는 테스트케이스는 다 돌려보았습니다. 다 정답이 나오구요

구현은 BFS를 이용하였구요 큐에서 빼서 상하좌우로 움직여보고 보드에 움직임이 없으면 큐에 넣지 않고 보드에 움직임이 있을 경우만 큐에 넣어주었습니다.

블럭 하나를 움직이는 함수가 두개인데 하나는 블럭이 보드 끝까지 움직이는 경우와 하나는 그렇지 않은 경우입니다.

혹시 반례가 있을까요?? 고수님들 도와주십셔 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int maxB = 0;
bool MoveRight(vector<vector<int>>& board);
bool MoveLeft(vector<vector<int>>& board);
bool MoveUp(vector<vector<int>>& board);
bool MoveDown(vector<vector<int>>& board);
void MoveOneBlock(int& b1, int& b2, int& b3, int& blank, bool& isChanged, bool& doubledBefore);
void MoveOneBlock2(int& b1, int& b2, int& blank, bool& isChanged, bool& doubledBefore);


int main() {
	freopen("input.txt", "r", stdin);
	int N;
	cin >> N;
	vector<vector<int>> board;
	queue<vector<vector<int>>> qu;
	queue<int> quMov;

	for (int i = 0; i < N; i++) {
		vector<int> line;
		int temp;
		for (int j = 0; j < N; j++) {
			cin >> temp;
			line.push_back(temp);
			if (temp > maxB) maxB = temp;
		}
		board.push_back(line);
	}

	qu.push(board);
	quMov.push(0);
	int mov;
	while (!qu.empty()) {
		board = qu.front();
		qu.pop();
		mov = quMov.front();
		quMov.pop();
		if (mov > 4) continue;

		/*for (int i = 0; i < board.size(); i++) {
			for (int j = 0; j < board[i].size(); j++) {
				cout << board[i][j] << " ";
			}
			cout << "\n\n";
		}*/

		vector<vector<int>> temp;
		temp = board;
		if (MoveUp(temp)) {
			qu.push(temp);
			quMov.push(mov + 1);
		}
		temp = board;
		if (MoveDown(temp)) {
			qu.push(temp);
			quMov.push(mov + 1);
		}
		temp = board;
		if (MoveLeft(temp)) {
			qu.push(temp);
			quMov.push(mov + 1);
		}
		temp = board;
		if (MoveRight(temp)) {
			qu.push(temp);
			quMov.push(mov + 1);
		}
		

	}

	cout << maxB;

	return 0;
}


bool MoveRight(vector<vector<int>>& board) {
	bool isChanged = false;
	bool doubledBefore = false; //직전에 두배가 되었음을 확인한다.
	int blank; //빈칸세기.
	for (int i = 0; i < board.size(); i++) {
		blank = 0;
		doubledBefore = false;
		for (int j = board.size()-1; j >= 0; j--) {//오른쪽에서부터 오른쪽으로 밀어넣는다.
			if (board[i][j] != 0) {//어떤 숫자가 들어있음.
				if (j + blank + 1 < board.size())
					MoveOneBlock(board[i][j], board[i][j + blank], board[i][j + blank + 1], blank, isChanged, doubledBefore);
				else
					MoveOneBlock2(board[i][j], board[i][j + blank], blank, isChanged, doubledBefore);
				
			}
			else {
				blank++;
				doubledBefore = false;
			}
		}
	}
	return isChanged;
}

void MoveOneBlock(int& b1, int& b2, int& b3, int& blank, bool& isChanged, bool& doubledBefore) { //b1은 옮기려는 블럭의 수, b2는 빈칸 끝, b3는 빈칸 끝에서 한칸 옆.
	if (b3 == b1 && !doubledBefore) { //옮기려는 숫자와 빈칸 끝에 있는 숫자가 같다면.
		b1 = 0;
		b3 *= 2;
		blank++;
		isChanged = true;
		doubledBefore = true;
		if (b3 > maxB) maxB = b3; //가장 큰 블럭인지 비교.
	}
	else if (blank != 0) { //같지 않거나 직전에 두배가 된 숫자이면서 빈칸이 있는 경우
		b2 = b1; //그냥 옮긴다.
		b1 = 0;
		isChanged = true;
		doubledBefore = false;
	}
}

void MoveOneBlock2(int& b1, int& b2, int& blank, bool& isChanged, bool& doubledBefore) { //b1은 옮기려는 블럭의 수, b2는 빈칸 끝.
	if (blank != 0) { //같지 않거나 직전에 두배가 된 숫자이면서 빈칸이 있는 경우
		b2 = b1; //그냥 옮긴다.
		b1 = 0;
		isChanged = true;
		doubledBefore = false;
	}
}

bool MoveLeft(vector<vector<int>>& board) {
	bool isChanged = false;
	bool doubledBefore = false;
	int blank; //빈칸세기.
	for (int i = 0; i < board.size(); i++) {
		blank = 0;
		doubledBefore = false;
		for (int j = 0; j < board.size(); j++) {//왼쪽에서부터 왼쪽으로 밀어넣는다.
			if (board[i][j] != 0) {//어떤 숫자가 들어있음.
				if (j - blank - 1 >= 0)
					MoveOneBlock(board[i][j], board[i][j - blank], board[i][j - blank - 1], blank, isChanged, doubledBefore);
				else
					MoveOneBlock2(board[i][j], board[i][j - blank], blank, isChanged, doubledBefore);
			}
			else {
				blank++;
				doubledBefore = false;
			}
		}
	}
	return isChanged;
}

bool MoveUp(vector<vector<int>>& board) {
	bool isChanged = false;
	bool doubledBefore = false;
	int blank; //빈칸세기.
	for (int i = 0; i < board.size(); i++) {
		blank = 0;
		doubledBefore = false;
		for (int j = 0; j < board.size(); j++) {//위쪽에서부터 위쪽으로 밀어넣는다.
			if (board[j][i] != 0) {//어떤 숫자가 들어있음.
				if (j - blank - 1 >= 0)
					MoveOneBlock(board[j][i], board[j - blank][i], board[j - blank - 1][i], blank, isChanged, doubledBefore);
				else
					MoveOneBlock2(board[j][i], board[j - blank][i], blank, isChanged, doubledBefore);
			}
			else {
				blank++;
				doubledBefore = false;
			}
		}
	}
	return isChanged;
}

bool MoveDown(vector<vector<int>>& board) {
	bool isChanged = false;
	bool doubledBefore = false;
	int blank; //빈칸세기.
	for (int i = 0; i < board.size(); i++) {
		blank = 0;
		doubledBefore = false;
		for (int j = board.size() - 1; j >= 0; j--) {//아래쪽에서부터 아래쪽으로 밀어넣는다.
			if (board[j][i] != 0) {//어떤 숫자가 들어있음.
				if (j + blank + 1 < board.size())
					MoveOneBlock(board[j][i], board[j + blank][i], board[j + blank + 1][i], blank, isChanged, doubledBefore);
				else
					MoveOneBlock2(board[j][i], board[j + blank][i], blank, isChanged, doubledBefore);
			}
			else {
				blank++;
				doubledBefore = false;
			}
		}
	}
	return isChanged;
}

yth1130 6년 전 0

아 그리고 본문에 적는 걸 깜빡했는데 4프로에서 막혔을 때는 최대 6번까지 움직이게 짰었습니다. 최대 5번까지로 제한하니까 4프로는 뚫더라구요

참고하시면 좋겠습니다. 12프로 뚫으신분은 도움 부탁드립니다 ㅠ

저도 4퍼센트에서 막히고 14퍼센트에서 막힌다음 뚫었습니다. 아마 대부분 막힌분들께서 2배를 해주기위해서 arr[i][j] 와 arr[i][j+1] 이 같은지를 검사하고 첫번째꺼를 두배로해주고 뒤에것을 0으로 해줬을건데, 이 방법이 생각해보니까 숫자사이에 0 이 없는 경우를 전제로 한 풀이더군요. 그래서 우선 숫자사이에 있는 0들을 고려하지 않도록 한쪽으로 몰아주는 작업이 필요합니다.

예를들어

0202

0000

이있다고하면 저방법으로하면 위의 2들은 합쳐지지 않습니다. 따라서 왼쪽으로 민다고치면,

2200

0000

으로 몰아주는 과정을 먼저 한뒤에 진행하여야 합니다.

jimjim 6년 전 0

2%에서 틀렸다고 떠서보시

위로 올리는 부분에서 문제가 있더라구요 저는 0 있는 부분 채우는 곳에서 에러가 있던데..

위의 코드는 열심히 살펴보지 않아서 잘 모르겠어요.

혹시나 도움이 될까해서 올립니다.

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

문제

문제

출처

ICPC

정말 어렵네요;; 4프로 뚫으니까 12?프로에서 막힙니다 ㅠ

yth1130 6년 전 0

yth1130 6년 전 0

changu02 6년 전 0

jimjim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말