백준 21609번 상어 중학교

문제 링크입니다: www.acmicpc.net/problem/21609

21609번: 상어 중학교

문제를 꼼꼼하게 읽어야하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 저 같은 경우 블록그룹을 정할 때, 무지개 블록들에 1 ~ M 색깔을 각각 칠하면서 가장 큰 블록그룹을 찾았습니다.

1.1 getBlockGroup 메서드 내 tempBoard가 무지개 블록들을 색깔 입힌 판이고, board는 기존 판입니다. 따라서, 구한 블록 그룹 내 무지개 블록 개수를 구할 수 있습니다.

1.2 가장 큰 블록 그룹을 찾을 때 BFS 알고리즘을 통해 구해줬습니다.

2. 1번에서 구한 가장 큰 블록 그룹에 속한 블록들을 제거해줍니다. (저 같은 경우 -2로 채웠습니다.)

3. 중력을 적용합니다. (gravity 메서드 참고)

4. 반시계 방향으로 판을 90도 회전해주고 (rotateBoard 메서드 참고)

5. 다시 중력을 적용해줍니다.

6. 1번에서 그룹을 못 찾을 때까지 1 ~ 5번을 반복해줍니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~