백준 11559. 뿌요뿌요

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

11559번: Puyo Puyo

 

뿌요뿌요의 법칙을 그대로 구현해야 한다.

 

우선 나는 12x6 으로 주어지는 입력을 받아서 90도 돌린 형태인 6x12 형태로 바꿔줬다.

이렇게 함으로서 주어지는 하나의 세로줄이 하나의 행이 되고, 같은 색끼리 터진 후에 빈 공간을 지워주면 뿌요들이 아래로 내려오는 형태가 된다.

 

4개 이상의 같은 색깔을 판단해야 하는데, bfs로 붙어있는 색들의 갯수를 찾고 4개 이상이라면 터트려 주고, 아니라면 터트리지 않도록 했다.

 

모든 칸들에 대하여 bfs 탐색을 진행해서 붙어있는 같은 색이 4개 이상인 뿌요들을 터트리도록 했다. 

만약 모든 칸들을 bfs 탐색을 했는데 터트린 뿌요가 하나도 없다면 더 이상의 연쇄는 불가능하기 때문에 프로그램을 종료한다. 

 

4개 이상 붙어있는 뿌요들을 터트린 후에는 뿌요들이 아래 공간이 있다면 내려와야 한다.

각 행들에 대하여 (아까 90도 돌려줬으므로) 11부터 0까지 비어있는 공간 ('.') 이라면 erase 해주고, 

행의 크기가 12가 될때까지 해당 행의 뒤에 빈 공간 ('.')을 push_back 해줬다.