백준 - Puyo Puyo

문제 출처: www.acmicpc.net/problem/11559

11559번: Puyo Puyo

의사 코드

1. '.'이 아닌 곳이 나오면 que에 넣고 8방 탐색을 한다.
2. 기준 색이랑 일치하면 boolean chk를 true로 해준다.
3. 기준 위치를 기준으로 일치하는 색이 4개 이상이면 해당 좌표를 '.'으로 바꾼다.
4. 각 열의 맨 아래부터 위로 탐색하면서
 4-1 색이 나올 때까지 cnt++
 4-1 색이 나오면 (x, y-cnt)부터  (x, y) 값을 대입 -> x, y는 현재 위치하는 좌표
5. 1부터 반복 

 

위처럼 초기 의사 코드를 작성하고 실행하니 바로 실패.. 아무래도 문제를 잘 못 읽은 거 같다. 다시 한번 문제 의도를 제대로 파악하려고 노력해보니 단순히 기준 좌표에서 8방 탐색이 아니라 상하좌우로 BFS탐색을 진행해야 한다는 걸 알았다.

물론 여기까지만 봐도 실패다..

 

다음으로는 배열을 재배치하는 코드에 문제가 있었다.

 

......
......
......
......
......
......
......
......
......
......
.... B.B
......
...B.B
......

 

일 경우 재배치가 불가능한 코드였다. 이를 해결하기 위해 que를 사용하였다.

이제는 확실히 통과할 거 같았지만... 결국 또 54%에서 에러가 발생했다. 

문제 지문에서 "터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한 번의 연쇄가 추가된다."

이 부분을 제대로 파악하지 못했다.

 

기존에 rearrange함수가 내부 while문 안에 존재했지만,  for문 밖으로 빼주었다.

 

전체 코드