[프로그래머스][카카오] 프렌즈4블록

문제

판이 주어지면 상하좌우 네 칸이 같으면 해당 칸은 사라지고 아래로 남은 블록들이 떨어진다. 지워지고 떨어지고를 반복할 때 지워지는 블록의 개수를 구하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/17679)

풀이

이 문제는 처음에 풀다가 이렇게 풀면 안될 것 같은데?하는 생각에 잠시 접어뒀던 문제인데 생각나서 다시 풀어봤습니다. 4칸이 같으면 해당 칸이 지워지고 남은 블록들을 아래로 떨어지게 해야합니다. BFS를 통해서 블록이 존재하는 판을 탐색하다가 상하좌우가 같으면 지우기 위한 리스트에 추가해줍니다. BFS 탐색이 끝나면 지워야하는 리스트를 지우며 지워지는 블록의 카운트를 세줍니다. 4칸 2개가 6개처럼 중첩되어 있을 경우가 있으니 체크를 해주며 카운트합니다. 한번의 BFS 탐색이 끝나면 블록을 아래쪽으로 밀어줍니다. 위에서 부터 차례대로 큐에 넣어주고 큐를 빼면서 밑에 칸부터 채워주어서 미는 부분을 구현했습니다. 여기까지가 처음에 풀었을 때 떠올렸던 부분이어서 거의 구현을 다했었는데 얼만큼 BFS탐색을 반복해야하고 끝내야하는지를 떠올리지 못했었습니다.(ㅠㅠ) BFS를 했을 때 지워지는 블록의 카운트를 세는데 이 카운트가 더이상 올라가지 않고 0이 될 경우에는 지워지는 블록이 없다는 뜻이므로 종료해주면 됩니다. 풀고나니 처음 생각했던대로 풀리고, 생각보다 쉽다는 생각이 들었는데 난이도 상이라고 적혀있어서 뿌듯했습니다.(*^^*)

(해설: http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/)

코드

https://github.com/kswim/Algorithm/blob/master/BFS/17679.cpp