#include "bits/stdc++.h" #define X first #define Y second using namespace std; // BFS로 블록 그룹 찾기 // 블록 그룹 탐색은 검은색(-1), 무지개(99)에서 시작하면 안되고, 크기는 2 이상 // 크기가 가장 큰 블록 그룹 탐색 기준은 블록 갯수 -> 무지개 갯수, 가장 나중에 찾은 그룹 순 // 탐색 기준이 넘어가는 기준은 갯수가 같을때 // 그룹을 찾으면 임시 vis 를 상단 원본 vis 에 copy // 그룹에 해당하는 좌표들을 erases 에서 전부 꺼내 원본 map 에 해당 좌표 0 처리 // 이떄 점수 계산 // 그 다음 map을 열, 행 순으로 순회하여 중력 처리 // 이때 행은 마지막 행 ~ 처음 행 순으로 순회, 가장 먼저 만나는 블록 내려주기 // 이떄 다른 블록이나 검은색 블록, 벽을 만나면 내리기 끝 // 그 다음 배열 회전, 원본 map 을 열, 행 순으로 순회, 이때 열은 마지막 열부터 // 인덱스 조정하여 복사본 map 에 행, 열 순으로 삽입 후 원본에 복사본 copy // 그 다음 다시 중력 처리 // 그 다음 다시 블록 그룹 탐색, 없으면 반복 종료 후 점수 출력 int main() { int n, m, score = 0; int map[20][20]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; cin >> n >> m; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ int num; cin >> num; // 무지개 블록은 99로 통일 if (!num) num = 99; map[i][j] = num; } } while(1){ int vis[20][20] = {}; int size = 0; // 가장 큰 블록 그룹 사이즈 int rainbow = 0; // 가장 큰 블록 그룹 무지개 블록 수 pair st = {0, 0}; // 가장 큰 블록 그룹 기준 블록 좌표 // 블록 그룹 탐색 for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ int vis_now[20][20] = {}; int size_now = 1; // 현재 블록 그룹 사이즈 int rainbow_now = 0; // 현재 그룹 무지개 블록 수 pair st_now = {i, j}; // 현재 그룹 기준 블록 좌표 // 검은색, 무지개 블록이면 그룹 탐색 X if (map[i][j] == -1 || map[i][j] == 99) continue; // 블록이 없어도 탐색 X if (map[i][j] == 0) continue; // BFS로 그룹 구하기 queue> Q; vis_now[i][j] = 1; Q.push({i, j}); while(!Q.empty()){ pair cur = Q.front(); Q.pop(); for(int dir = 0; dir < 4; ++dir){ int nx = cur.X + dx[dir]; int ny = cur.Y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (vis_now[nx][ny] == 1) continue; // 검은색 블록, 빈 블록 무시 if (map[nx][ny] == -1 || map[nx][ny] == 0) continue; // 다른 색깔 블록 무시, 무지개 블록은 제외 if (map[nx][ny] != 99 && map[nx][ny] != map[i][j]) continue; vis_now[nx][ny] = 1; // 무지개 블록 카운팅 if (map[nx][ny] == 99) rainbow_now++; // 기준 블록 갱신 if (st_now > make_pair(nx, ny)) st_now = {nx, ny}; size_now++; Q.push({nx, ny}); } } // 현재 사이즈가 1 이하면 그룹 X // 현재 사이즈가 가장 큰 그룹 사이즈보다 작으면 갱신 X if (size_now < 2 || size > size_now) continue; // 현재 사이즈 = 가장 큰 그룹 사이즈 라면 무지개 블록 수 비교 // 현재 무지개 블록 수가 더 작으면 갱신 X else if (size == size_now && rainbow > rainbow_now) continue; // 현재 기준 블록 < 가장 큰 그룹 기준 블록 이면 갱신 X else if (st > st_now) continue; // 가장 큰 그룹 정보 갱신 size = size_now; rainbow = rainbow_now; st = st_now; copy(vis_now[0], vis_now[0] + 20 * 20, vis[0]); } } if (size == 0) break; // 더이상 블록 그룹이 없음, 끝 // 가장 큰 블록 그룹 좌표 순회 int score_now = 0; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ // map 에서 블록 삭제와 점수 기록 if (vis[i][j] == 1){ map[i][j] = 0; score_now++; } } } score += score_now * score_now; // map 중력 처리 for(int j = 0; j < n; ++j){ // 열, 행 순으로 순회 // 행은 마지막 행 ~ 처음 행 순으로 순회, 가장 먼저 만나는 블록 내려주기 for(int i = n - 1; i >= 0; --i){ // 검은색, 빈 블록 이면 무시 if (map[i][j] < 1) continue; // 내려주기, 다음 칸이 빈 블록이 아니면 막힘 int k; for(k = i; k + 1 < n; ++k) if (map[k + 1][j]) break; // 내린 블록 정보 갱신 map[k][j] = map[i][j]; // 안내려갔으면 빈칸 처리 X if (k != i) map[i][j] = 0; } } // map 90도 반시계 방향 회전 int map_cpy[20][20]; // 복사본 map // map을 열, 행 순으로 순회, 이때 열 시작은 마지막 열 for(int j = n - 1; j >= 0; --j){ for(int i = 0; i < n; ++i) // 회전 후 map 정보값을 인덱스 조정하여 복사본에 기록 map_cpy[abs(j - (n - 1))][i] = map[i][j]; } // 회전 끝나면 원본에 복사본 copy copy(map_cpy[0], map_cpy[0] + 20 * 20, map[0]); // 다시 map 중력 처리 for(int j = 0; j < n; ++j){ for(int i = n - 1; i >= 0; --i){ if (map[i][j] < 1) continue; int k; for(k = i; k + 1 < n; ++k) if (map[k + 1][j]) break; map[k][j] = map[i][j]; if (k != i) map[i][j] = 0; } } } cout << score << endl; return 0; }

제출 #137383

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: