글 읽기 - 반례 들어주실 수 있나요

cid_cat 2년 전 0

테스트 코드는 다 통과하는데 채점 시작하자마자 '틀렸습니다'로 나오네요.

빈 칸은 -2 로 채우고

(1) 최대 크기 블럭 찾기(FindBlock) -> (2) 터트리고 점수 계산(PopBlock) ->(3) 중력 작용(DropDown) -> (4) 반시계 회전(Rotate) ->(5) 중력 작용(DropDown) 순서대로 수행하였고 2 이상의 최대 크기 블럭이 없는 경우 종료하도록 하였습니다.

FindBlock과 PopBlock은 DFS를 사용해 구현하였고, FindBlock에서 얻은 기준 좌표로 PopBlock을 수행합니다.

기준 좌표를 얻은 방법은 Info 구조체를 설정하여 1. 블럭 크기 2. 무지개 블럭 수 3. 행 4. 열 순으로 정렬해 구했습니다.

반례가 되는 예시나 틀린 부분 찾아주실 수 있을까요? ㅠㅠ

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

#define DEBUG_PRINT

const int MAX = 20;
int map[MAX][MAX];
bool bVisited[MAX][MAX];

int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { -1, 0, 1, 0 };

int N, M;
int nRainbowNum;
int nAnswer;

std::vector<std::pair<int, int>> vecRainbow;

// -1: Black
//  0: Rainbow
// -2: Blank

struct Info
{
	int _y, _x;
	int _nLength;
	int _nRainbowNum;

	// 우선순위 블럭 정렬
	const bool operator < (const Info& other)
	{
		// 내림차순
		if (this->_nLength == other._nLength) {
			if (this->_nRainbowNum == other._nRainbowNum) {
				if (this->_y == other._y) {
					return this->_x > other._x;
				}
				return this->_y > other._y;
			}
			return this->_nRainbowNum > other._nRainbowNum;
		}
		return this->_nLength > other._nLength;
	}
};

void Solve();
bool Play();
bool FindBlock(int& retY, int& retX);
int DFS(int y, int x, int number);
int PopBlock(int y, int x, int number);
void DropDown();
void Rotate();

#ifdef DEBUG_PRINT
void DebugPrint(std::string strTitle);
#endif

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

	std::cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int temp;
			std::cin >> temp;
			map[y][x] = temp;

			// rainbow block 관리
			if (temp == 0)
				vecRainbow.push_back(std::make_pair(y, x));
		}
	}

	Solve();

	return 0;
}

void Solve()
{
	bool bPlayed = true;

	while (bPlayed) {
		bPlayed = Play();
	}

	std::cout << nAnswer << "\n";
}

bool Play()
{
	// Find Biggest Block (DFS)
	// 기준 블럭 좌표 반환
	int y, x;
	bool bFind = FindBlock(y, x);
	if (bFind) {
#ifdef DEBUG_PRINT
		std::cout << "##### [DEBUG] Position (y: " << y << ", x: " << x << ") #####\n";
		// Pop
		memset(bVisited, false, sizeof(bVisited));
		bVisited[y][x] = true;
		// 기준 블럭 터트리기 (DFS)
		int blockLength = PopBlock(y, x, map[y][x]);
		nAnswer += blockLength * blockLength;

		DebugPrint("PopBlock");
		// Drop Down
		DropDown();
		DebugPrint("DropDown1");
		// Rotate CCW
		Rotate();
		DebugPrint("Rotate");
		// Drop Down
		DropDown();
		DebugPrint("DropDown2");
#else
		// Pop
		memset(bVisited, false, sizeof(bVisited));
		bVisited[y][x] = true;
		int blockLength = PopBlock(y, x, map[y][x]);
		nAnswer += blockLength * blockLength;

		// Drop Down
		DropDown();
		// Rotate CCW
		Rotate();
		// Drop Down
		DropDown();
#endif
		return true;
	}
	else
		return false;	
}

bool FindBlock(int& retY, int& retX)
{
	int nMax = 2;
	std::vector<Info> vecInfo;
	memset(bVisited, false, sizeof(bVisited));

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] <= 0 || bVisited[y][x])
				continue;

			// 색깔있는 블럭
			int length = 0;
			bVisited[y][x] = true;

			nRainbowNum = 0;
			length = DFS(y, x, map[y][x]);

			// 길이, rainbow 블럭 수, 기준좌표 등록
			Info info;
			info._y = y;
			info._x = x;
			info._nLength = length;
			info._nRainbowNum = nRainbowNum;

			// 길이 2이상, 이전까지 최대 크기보다 같거나 큰 경우 등록
			if (nMax <= length) {
				nMax = length;
				vecInfo.push_back(info);
			}

			// rainbow 되돌리기
			for (auto elem : vecRainbow) {
				bVisited[elem.first][elem.second] = false;
			}
		}
	}

	// 후보들 중 고르기
	std::sort(vecInfo.begin(), vecInfo.end());

	// 길이 2 이상 블럭이 없는 경우 멈춤.
	if (!vecInfo.size())
		return false;

	retY = vecInfo[0]._y;
	retX = vecInfo[0]._x;
	return true;
}

int DFS(int y, int x, int number)
{
	int nRet = 1;
	// rainbow 블럭 수 체크
	if (map[y][x] == 0)
		nRainbowNum++;

	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || ny >= N || nx < 0 || nx >= N)
			continue;
		if (map[ny][nx] < 0 || bVisited[ny][nx])
			continue;

		if (map[ny][nx] == number || map[ny][nx] == 0) {
			bVisited[ny][nx] = true;
			nRet += DFS(ny, nx, number);
		}
	}

	// 길이 반환
	return nRet;
}

int PopBlock(int y, int x, int number)
{
	// DFS와 동일
	// 빈 칸: -2
	map[y][x] = -2;

	int nRet = 1;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || ny >= N || nx < 0 || nx >= N)
			continue;
		if (map[ny][nx] < 0 || bVisited[ny][nx])
			continue;

		if (map[ny][nx] == number || map[ny][nx] == 0) {
			bVisited[ny][nx] = true;
			nRet += PopBlock(ny, nx, number);
		}
	}

	return nRet;
}

void DropDown()
{
	for (int x = 0; x < N; x++) {
		for (int y = N - 1; y >= 0; y--) {
			if (map[y][x] < 0)
				continue;

			int val = map[y][x];
			map[y][x] = -2;

			int ty = y;
			while (ty < N) {
				int ny = ty + 1;

				if (ny >= N) {
					map[ty][x] = val;
					break;
				}
				else if (map[ny][x] == -1 || map[ny][x] >= 0) {
					map[ty][x] = val;
					break;
				}
				else if (map[ny][x] == -2) {
					ty++;
				}
			}
		}
	}
}

void Rotate()
{
	// CCW 회전
	int mapCopy[MAX][MAX];
	memcpy(mapCopy, map, sizeof(map));

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			map[y][x] = mapCopy[x][N - 1 - y];
		}
	}
}

#ifdef DEBUG_PRINT
void DebugPrint(std::string strTitle)
{
	std::cout << "##### [DEBUG]: " << strTitle.c_str() << " #####\n";
	for (int y = 0; y < N; y++){
		for (int x = 0; x < N; x++){			
			std::cout <<std::setw(2)<< map[y][x] << " ";
		}
		std::cout << "\n";
	}
	std::cout << "\n";
}
#endif

cid_cat 2년 전 1

자답] map을 입력받을 때 vecRainbow로 좌표를 저장해 방문 여부를 체크했는데,

중력, 회전할 때 위치 업데이트가 안 되었네요.

수정해서 통과했습니다.

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

문제

문제

출처

ICPC

반례 들어주실 수 있나요

cid_cat 2년 전 0

cid_cat 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말