백준 21609. 상어 중학교

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

 

문제에서 요구하는 기능들을 하나씩 하나씩 잘 구현해주면 되는 문제였다. 

전체적으로 크게보면 네가지 기능을 구현해야 한다. 

 

 

1.크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.

 

나는 그룹 구조체를 다음과 같이 만들어 줬다.

struct Group
{
    int size; // 그룹 크기
    int rainbow; // 레인보우 블록의 수
    int r; // 기준 블록 행, 열
    int c;
    vector<pair<int,int>> blocks; // 블록들 위치
};

그리고 bfs 알고리즘으로 모든 그룹들의 정보를 저장하고 1번 조건에 맞는 cmp 함수를 만들어서 sort 해서 첫 번쨰 요소가 조건에 맞는 그룹이 되도록 했다.

 

 

2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.

빈 공간은 -2로 정의하고, 그룹 구조체에 블록들의 위치 정보를 저장했으므로 그 정보를 토대로 블록을 제거해 줬다. 

 

3. 격자에 중력이 작용한다.

격자와 같은 크기의 2차원 배열을 하나 더 만든 후에, 격자의 하나의 열을 기준으로 아래에 있는 검정 블록을 제외한 블록부터 새로운 격자에 검정 블록이나 범위를 벗어날때까지 아래로 내려줬다. 이렇게 하면 검정 블록을 제외한 블록들이 제자리를 찾게 된다. 

 

4. 격자가 90도 반시계 방향으로 회전한다.

90도 반시계 방향으로 회전한다는 것은 격자의 0열은 N-1열로, 1열은 N-2열로 이동하는 것과 같다.