https://www.acmicpc.net/problem/11559
문제
> 뿌요뿌요의 룰은 다음과 같다.
1. 필드에 여러 가지 색깔의 뿌요를 놓는다.
뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
2. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.
이때 1연쇄가 시작된다.
3. 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면,
역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
4. 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데,
터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
5. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
> 남규는 최근 뿌요뿌요 게임에 푹 빠졌다.
> 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다.
> 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다.
> 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!접근
입력으로 들어오는 뿌요필드를 행과 열을 감소연산자를 이용한 반복문으로 역순으로 받아 바닥이 0,0부터 오도록 재정렬해준다.
BFS사용해서 연쇄를 찾아야하므로 현재 필드에서 각 좌표(뿌요)마다 사방탐색을 하며 뿌요가 터지는 조건(4개이상)을 만족하는지 본다.
4개 이상을 만족하면 연결되어있는 뿌요들의 좌표를 rst라는 벡터에 모아두고
BFS가 끝날 때마다 이를 뿌요를 아래로 밀기 전에 연쇄로 터지는 애들을 모아놓는 Pops라는 벡터에 추가한다.
그럼 0,0부터 12,6까지 싹 돌고나면 pops에 연쇄된 4개 이상이 모인 뿌요들의 좌표들이 전부 저장이 되어있다.
이 좌표들을 역순으로 정렬해준 뒤 각 좌표를 꺼내서 다음 행에 있는 좌표값들로 차례대로 덮어 써준다.
(위에서 아래로 한칸씩 밀리는건 행만 보면 되므로 열은 고정하고 민다.)
(만약 (1,5)가 터진다면 2,5와 3,5...11,5에 있던 애들이 차레대로 -1행위치로 덮어써지고 11,5자리에는 공백을 나타내는'.'을 넣어준다.)
pops의 모든 좌표에 대해 덮어쓰는 작업이 끝나면 터지는 횟수를 1회 누적한다.
그리고 while문을 통해 덮어써서 새로 만들어진 필드를 다시 탐색한다.
이렇게 누적된 cnt를 출력한다.
문제해결
> 뿌요들의 위치를 저장할 field벡터와 BFS에서 뿌요의 방문처리를 담당할 visited벡터, 4개 이상이 쌓여 이제 터져야하는 뿌요들의 좌표를 저장할 Pops벡터를 선언해주고
뿌요가 터져서 터지는 횟수를 저장할 rcnt 변수도 선언해준다.
> 뿌요가 터졌을 때 뿌요를 아래로 밀어 좌표를 다시 써주는 Remake메소드를 정의한다.
> 입력으로 pops안에 있는 좌표를 받고 열은 필요없으므로 들어온 열 좌표를 그대로 사용하며
행 좌표만 반복문을 통해 들어온 좌표+1에 있는 애들을 순차적으로 덮어 써주면 갱신한다.
마지막으로 젤 끝에있는 11,col 좌표를 공백으로 채워준다.
> 연결된 뿌요를 탐색하는 BFS 메소드를 정의한다. 입력받은 좌표를 시작으로 큐에 넣으며 사방 탐색으로 필드 내에 존재하는 같은 색을 가진 뿌요를 탐색한다.
큐에 있는 뿌요를 꺼내면서 방문안헀던 뿌요라면 이 좌표를 rst라는 연결된 뿌요를 저장하는 벡터에 저장하며 cnt를 누적한다.
> 탐색이 끝나면 cnt값을 보고 이 값이 4이상이면(터지는 조건) rst에 저장된 좌표를 터트리기 위해 터질 애들을 모아놓은 pops벡터에 이를 전달해준다.
> main함수에서 뿌요 필드를 역순으로 입력받아 0,0부터 처리할 수 있도록 정렬해준다.
> while문 내부에서 뿌요 게임을 돌린다. 판이 remake로 새로 정렬 될 때마다 0,0부터 다시 BFS탐색을 하므로 방문처리 벡터를 while내부에서 매번 초기화한다.
> 공백인 좌표는 넘어가고 아직 방문 안한 좌표를 BFS에 넣으면서 연쇄된 애들을 찾는다. (이때, BFS내부에서 4개이상이 있으면 pop에 저장됨)
> 만약 pops안에 아무것도 없으면 터질 수 있는 뿌요가 없다는 것이므로 바로 while문을 깨고 나와 rcnt인 터진 횟수를 출력한다.
> pops에 터질 애들이 있으면 터질 애들을 역순으로 정렬하고(위에 있는 뿌요들부터 아래로 차례대로 밀기위해) Remake메소드를 호출해 pops에 있는 애들에 전부 필드 다시쓰는 작업을 해준다.
> 필드가 다시 만들어지면 또 터질 애들이 있나 봐야하므로 부울 값 again을 true로 주면서 while문이 다시 돌아가게 해주고 터질 애들이 없으면 again이 그대로 false라서 while문이 깨진다.
> while문이 한번 돌아간다는건 한번 터짐에 대한처리인데 연쇄로 몇번이 터지던 이것도 한번으로 치므로 한번으로 처리된다. 그래서 while문의 마지막에 rcnt를 누적해준다.
< 최종적으로 누적된 rcnt를 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
vector<vector<char>> field;
vector<vector<bool>> visited;
vector<pair<int, int>> pops;
int rcnt = 0;
void Remake(pair<int, int> r)
{
for (int i = r.first; i < 11; i++)
{
field[i][r.second] = field[i + 1][r.second];
}
field[11][r.second] = '.';
}
void BFS(pair<int, int> start)
{
queue<pair<int, int>> q;
q.push(start);
vector<pair<int, int>> rst;
bool valid = false;
char c = field[start.first][start.second];
int cnt = 0;
while (!q.empty())
{
int fr = q.front().first;
int fc = q.front().second;
q.pop();
if (visited[fr][fc]) continue;
visited[fr][fc] = true;
cnt++;
rst.push_back({ fr, fc });
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= 12) continue;
if (nc < 0 || nc >= 6) continue;
if (field[nr][nc] == c)
{
q.push({ nr,nc });
}
}
}
if (cnt >= 4)
{
for (auto a : rst)
pops.push_back(a);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
field.resize(12, vector<char>(6));
visited.assign(12, vector<bool>(6, false));
for (int i = 11; i >= 0; i--)
{
for (int j = 5; j >= 0; j--)
{
cin >> field[i][j];
}
}
while (1)
{
bool again = false;
pops.clear();
visited.assign(12, vector<bool>(6, false));
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 6; j++)
{
if (field[i][j] == '.') continue;
if (visited[i][j]) continue;
BFS({ i, j }); //4개짜리가 있으면
}
}
if (!pops.empty())
{
sort(pops.rbegin(), pops.rend());
for (auto a : pops)
Remake(a);
again = true;
}
if (!again) break;
rcnt++;
}
cout << rcnt << '\n';
}
후기
연쇄에 대한 부분을 제대로 이해하지 못해 잘못된 방향으로 처리를 했다.
BFS내부에서 4개일 때마다 필드 재정리 해주고 부울 값으로 "터졌다"를 넘겨
main의 while문이 다시 돌아가도록 했다.
이는 예제를 넣으면 횟수는 3으로 제대로 나와도 연쇄를 1로 치면서 3번이 아닌
연쇄안에서 터진애들을 각각 1로 쳐서 나온 결과이다.
즉 연쇄로 3번 터짐, 1번터짐, 1번 터짐 이면 총 3인데
내 원래 방식으로 보면 5가 나오게 되는것이다.
이를 while문에서 일단 BFS로 모든 좌표에 대해 다 획인 해서 연쇄를 골라내고
마지막에 필드 Remake를 해주면서 이 때 횟수를 누적해주는걸로 수정해 맞았다.
