[백준 11559번] Puyo Puyo - java

문제 설명

1. 12줄 - 6칸짜리 보드가 있다.

2. .과 각각의 색깔로 구분되는 뿌요가 주어진다.

3. 뿌요가 상하좌우로 같은 색의 뿌요가 있으면 터진다. 중요한 점은 여러 뿌요들이 터져야 하는 경우 동시에 터지고, 1연쇄가 늘어난다.

4. 아래 뿌요가 터지면 위의 뿌요가 내려온다. 이렇게 전체 뿌요를 구하면 된다.

풀이 과정

 1. 오늘 진행된 데브매칭 3번문제와 거의 유사한 문제이다... 해당 문제는 진짜 거의 다 풀었는데 시간이 넘어서 못풀었다. 그래서 아쉬워서 이 문제라도 풀었다...

 2. BFS를 사용하고, 이전에 풀었던 2048(easy)에서의 정렬 방식을 참고하면 간단히 구현할 수 있다.

 3. 간단하게 코드에 대해 설명하자면

- 하나씩 char로 하면 귀찮으니까 01 2 3 4 ... 이렇게 숫자로 바꾸어 준다.

- 위, 아래, 오른, 왼 코드를 하나씩 만들어서 모든 경우를 탐색한다 (위 - 위 - 위 - 위 - 위), (위, 위, 위, 위, 아래) ......

- 보드의 x y 축을 가져와서 여기다가 BFS를 사용해 해당 위치의 값들을 저장하면 된다.

- 기존의 뿌요가 있는 map에서 1번의 process에서 모든 경우를 완전탐색하여 터지게 하고(여기서 완전탐색을 사용하는 이유는 모든 map의 뿌요들을 동시에 터지게 하기 위함), 그 값을 newMap에 저장한다. 터지게 되면 boolean에서 true로 하여 다시 process를 진행한다. 안터지면 더이상 할 이유가 없음.

위에서 터진 경우 - 그렇게 구해진 newMap은 중력이 적용되지 않은 것이다. 나는 문제의 보기와 똑같은 배열을 만들어서 배열의 11에서부터 뿌요를 넣어주었다. 그러므로 중력이 주어지는 경우 Queue를 사용하면 간단히 값들을 중력이 적용된 값으로 만들 수 있을 것이다. 이를 mapGravity로 정의하여 만들고, 이후 map에 저장한다. 그리고 터졌으니 ans를 하나 증가시킨다.

- 저렇게 터졌으면 다시 위의 process를 진행하면 된다. 굉장히 쉬운 문제이나 구현이 시간이 조금 걸린다.... 

 

코드