A. 문제설명
https://www.acmicpc.net/problem/11559
문제에 대한 자세한 설명은 링크 참조
1. 12*6 푸요푸요 게임판이 주어짐
2. 필드에 R/G/B/Y 뿌요를 놓음. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어짐
3. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어짐
4. 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어짐
5. 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지고 연쇄 작용이 일어남
6. 상대방의 필드가 주어졌을 때, 몇 연쇄가 일어날 지 예측할 것
B. 접근법
BFS
1. 푸요푸요의 연쇄작용 계산 / 2. 중력으로 인한 푸요들의 떨어짐
이 문제에 대한 접근은 크게 다음의 두개로 나누어 생각할 수 있다.
1. 우선, 각 푸요가 상하좌우로 길이 4개 이상 같은 색으로 연결된 것들을 찾아 연쇄작용이 일어날 부분을 찾아야 한다. 이는 배열의 각 좌표에서 주변을 BFS로 탐사하는 방법으로 접근이 가능하다.
2. 이후, 푸요푸요의 연쇄작용이 일어나, 해당 푸요들이 게임판에서 전부 사라지면 중력으로 인해 푸요들이 떨어지는 부분만 게임판의 열들에 대해서 밀어내어 구현하면 된다.
C. 풀이
1. 게임판 푸요의 연쇄작용이 더 이상 없을때까지 while문 수행, 여기서 모든 게임판의 엔트리에서 BFS 함수를 호출한다.
2. 게임판의 각 엔트리에서 puyo_bfs() 함수가 호출되면, 해당 위치에서 상하 좌우를 탐사하며 주변 푸요를 BFS로 탐색
3. 만약, 주변에 같은 색의 푸요를 찾았다면 큐에 해당 푸요를 넣고 탐사 진행 반복, 푸요의 길이가 4가 넘는 애들에 대해서 연쇄표시
4. 처음에 푸요 탐사함수가 연쇄로 없어질 푸요를 puyoArr에 표기후 Arr에서 직접 없앤다
5. 각 열에 대해 호출하여 모든 열을 없어진 푸요를 제외하고 모두 아래로 밈
6. 모든 연쇄가 끝날 때까지 해당 작업을 반복하고, 완료시 연쇄가 일어난 횟수를 반환한다.
D. 내 코드
