문제 출처
1. 문제설명
- 우리가 알고 있는 뿌요뿌요 게임과 매우 비슷하다.
- 상,하,좌,우로 인접한 뿌요가 같은색이면서 4칸이상 연속으로 배치되어 있다면 터진다.
- 처음 뿌요는 항상 아래쪽에 배치되어 있다.
2. 알고리즘 설계
- BFS 또는 DFS로 뿌요를 확인하고, 터트리는..
- 그래프 문제이면서, 시뮬레이션 문제이다.
- 터트리는 구현
- 본인은 BFS를 이용하였다.
- BFS로 같은 색이라면 전진하면서 큐에 담는다. 동시에 임시 벡터에도 담는다.
- 탐색이 끝났다면, 임시 벡터의 크기가 4 이상인지 확인하고
.
으로 변경한다.
for (pii pos : tmp)
board[pos.Y][pos.X] = '.';
- 뿌요의 위치를 옮겨주는 기능
- 뿌요가 터졌다면, 아래로 떨어지게 된다.
- 높이
H
가 되거나 .
이 아닌 지점까지 내려주면 된다.
while (tmp + 1 < H && board[tmp + 1][i] == '.') {
swap(board[tmp][i], board[tmp + 1][i]);
tmp++;
}
3. 전체 코드
4. 소감
- 코드를 보면 알 수 있듯이,
swap()
은 내가 구현한 게 아니다.
- 헤더파일
<algorithm>
에 구현되어 있다.
- 일부 범위를 바꾸는
swap_ranges()
라는 함수도 있다.
- 자세한 내용은 여기를 참고해주세요!