백준 11559번 (Puyo Puyo, C++) / 추가 반례 [BAEKJOON]

글쓴이 / / BaekjoonOnlineJudge, C++/CPP
목차 테이블
  1. Puyo Puyo

Puyo Puyo

https://www.acmicpc.net/problem/11559

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초256 MB183917238522937.817%

문제

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 

뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 

연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면,

역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데,

터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고

여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다.

이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만,

상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다.

하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다.

상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

입력

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.

이때 .은 빈공간이고 .이 아닌 것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 

즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

출력

현재 주어진 상황에서 몇 연쇄가 되는지 출력한다. 

하나도 터지지 않는다면 0을 출력한다.

예제 입력 1

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

예제 출력 1

3

출처

University > 연세대학교 > 2015 연세대학교 프로그래밍 경시대회 C번

  • 빠진 조건을 찾은 사람: doju
  • 문제의 오타를 찾은 사람: jh05013
  • 데이터를 추가한 사람: measurezero
  • 문제를 만든 사람: zych1751

알고리즘 분류

추가 반례

예제 입력 A

Y...YR
B.RGGY
R.GGYY
G.RYGR
YGYGRR
YBRYGY
RRYYGY
YYRBRB
YRBGBB
GBRBGR
GBRBGR
GBRBGR

예제 출력 A

14

예제 입력 B

......
......
......
......
......
......
......
B.....
R.....
R.....
R.....
RBBB..

예제 출력 B

2

예제 입력 C

......

......

......

......

......

......

......

......

......

......

......

......

예제 출력 C

0

예제 입력 D

......
......
......
......
......
......
......
......
...YP.
.PYYYP
PBPPPR
BBBRRR

예제 출력 D

2

12개의 줄 / 줄은 6개의 문자
.은 빈 공간
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 
즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

BFS로 검색 / 4개 이상이면 전부 . 로 변경하고 모든 칸이 검색이 완료되면 뿌요를 아래로 이동
이동이 없을 때 까지 반복하며 카운트를 올린다.

입력 확인 코드

#include<iostream>

using namespace std;

char map[12][6] = { '.' };
bool check[12][6] = { false };


void Initalization()
{

	for (int i = 0; i <= 11; i++)
	{ // 세로
		for (int j = 0; j <= 5; j++)
		{ // 가로
			cin >> map[i][j];
		}
	}
}

int main()
{
	Initalization();

	cout << "\n------------------------\n";
	for (int i = 0; i <= 11; i++)
	{ // 세로
		for (int j = 0; j <= 5; j++)
		{ // 가로
			cout << map[i][j];
		}
		cout << "\n";
	}

	return 0;
}

중간 점검 코드

#include<iostream>
#include <queue>
#include <list>

using namespace std;

queue<pair<int, int>> myqueue;
list<pair<int, int>> ::iterator iter;

char map[12][6] = { '.' };
bool check[12][6] = { false };
int result = 0;


int D[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
// 좌우상하

void Initalization()
{

	for (int i = 0; i <= 11; i++)
	{ // 세로
		for (int j = 0; j <= 5; j++)
		{ // 가로
			cin >> map[i][j];
		}
	}
}

void BFS(int i , int j, char ch)
{
	myqueue.push(make_pair(i, j));
	list<pair<int, int>> mylist;

	while (!myqueue.empty())
	{
		pair<int, int> pair = myqueue.front();
		check[pair.first][pair.second] = true; // 방문 마킹
		mylist.push_back(pair); // 리스트에 넣음 나중에 카운트
		myqueue.pop();

		for (int k = 0; k < 4; k++)
		{
			// 상하 좌우로 검색
			int nx = pair.first + D[k][0];
			int ny = pair.second + D[k][1];

			// 맵의 범위를 넘어감 // 빈공간 // 같은 문자가 아닐 경우 넘어감  
			if (nx < 0 || nx > 12 || ny < 0 || ny > 6 || check[nx][ny] == true || map[nx][ny] == '.' || map[nx][ny] != ch)
			{
				continue;
			}

			myqueue.push(make_pair(nx, ny));
		}
	}
	
	// 만약 연결된 뿌요가 4개 이상이라면 
	if (mylist.size() >= 4)
	{
		for (iter = mylist.begin(); iter != mylist.end(); iter++)
		{
			map[iter->first][iter->second] = '.';
		}

		result++;
	}

}


int main()
{
	Initalization();

	for (int i = 0; i <= 11; i++)
	{ // 세로
		for (int j = 0; j <= 5; j++)
		{ // 가로

			if (check[i][j] != true && map[i][j] != '.')
			{
				BFS(i, j, map[i][j]);
			}	
		}
	}
	
	cout << "result : " << result;

	cout << "\n------------------------\n";
	for (int i = 0; i <= 11; i++)
	{ // 세로
		for (int j = 0; j <= 5; j++)
		{ // 가로
			cout << map[i][j];
		}
		cout << "\n";
	}

	return 0;
}

이제 . 보다 위에 있는 알파벳을 아래로 내려주고
result 값을 저장하고 값이 변화되지 않을 때까지 반복해주면 될 것 같다.
배열도 약간 수정

통과된 코드

#include <iostream>
#include <queue>
#include <list>
#include <string>
#include <algorithm>

using namespace std;

queue<pair<int, int>> myqueue;
list<pair<int, int>> ::iterator iter;

char map[6][12];
bool check[6][12];
int result = 0;

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

void Initalization()
{
	// 초기화
	for (int j = 0; j <= 11; j++)
	{ // 세로
		for (int i = 0; i <= 5; i++)
		{ // 가로
			map[i][j] = '.';
			check[i][j] = false;
		}
	}

	for (int y = 0; y <= 11; y++)
	{ // 세로
	
		for (int x = 0; x <= 5; x++)
		{ // 가로

			cin >> map[x][y];
		}
	}
}

void BFS(int i , int j, char ch)
{
	myqueue.push(make_pair(i, j));
	list<pair<int, int>> mylist;

	while (!myqueue.empty())
	{
		pair<int, int> pair = myqueue.front();
		check[pair.first][pair.second] = true; // 방문 마킹
		mylist.push_back(pair); // 리스트에 넣음 나중에 카운트
		myqueue.pop();

		for (int k = 0; k < 4; k++)
		{
			// 상하 좌우로 검색
			int nx = pair.first + dx[k];
			int ny = pair.second + dy[k];

			// 맵의 범위를 넘어감 // 빈 공간 // 같은 문자가 아닐 경우 넘어감  
			if (nx < 0 || nx > 5 || ny < 0 || ny > 12 || check[nx][ny] == true || map[nx][ny] == '.' || map[nx][ny] != ch)
			{
				continue;
			}

			myqueue.push(make_pair(nx, ny));
		}
	}

	// 만약 연결된 뿌요가 4개 이상이라면 
	if (mylist.size() >= 4)
	{
		for (iter = mylist.begin(); iter != mylist.end(); iter++)
		{
			map[iter->first][iter->second] = '.';
		}

		result++;
	}
}


int main()
{
	Initalization();

	int tempResult = -1;

	while (result != tempResult)
	{
		tempResult = result;

		for (int j = 0; j <= 11; j++)
		{ // 세로
			for (int i = 0; i <= 5; i++)
			{ // 가로
				if (check[i][j] != true && map[i][j] != '.')
				{
					BFS(i, j, map[i][j]);
					// 방문 초기화
				}
			}
		}

		for (int x = 0; x <= 5; x++)
		{
			string tempStr = "";
			for (int y = 0; y <= 11; y++)
			{
				if (map[x][y] != '.')
				{
					tempStr.push_back(map[x][y]);
				}
			}
			string temp2;
			for (int temp = 11 - tempStr.size(); temp >= 0; temp--)
			{
				temp2.push_back('.');
			}

			tempStr = temp2 + tempStr;

			for (int y = 0; y <= 11; y++)
			{
				map[x][y] = tempStr[y];
			}
		}

		for (int j = 0; j <= 11; j++)
		{ // 세로
			for (int i = 0; i <= 5; i++)
			{ // 가로
				check[i][j] = false;
			}
		}

		if (tempResult != result)
		{
			result = tempResult + 1;
		}

	}

	cout << result;

	return 0;
}

로직

BFS로 검색해서 상하좌우로 4개 이상 연속되는 알파벳을 리스트에 담고 전부 . 로 바꾸어준다.
(여러 그룹이 터지더라도 1번으로 친다.)

마킹도 풀어주자

알파벳 아래 . 이 있으면 안됨
난 string 값으로 바꾸어서 처리

값이 변하지 않을 때까지 반복

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

관련 게시물

백준 2583번 (영역 구하기, C++) [BAEKJOON]

백준 2583번 (영역 구하기, C++) [BAEKJOON]

BaekjoonOnlineJudge, C++/CPP / 글쓴이 / / , , , , , , , , , , , , , , , , , , , , , ,

백준 2583번 '영역 구하기' 문제에 대한 글입니다. BFS 알고리즘을 이용하여 해결하였습니다. (This…

위로 스크롤