꽤 오랜 시간이 걸렸다.
내 풀이는 조금 복잡한데, 키포인트는 두개였다.
1. 그룹 내에서는 일반 블록이 적어도 하나 존재하므로, 2중 for문을 돌면서 일반 블록을 만날 때 마다 해당 위치를 임시 기준블록으로 취한 뒤 dfs를 진행한다. 그리고 여기서 그룹을 만들어나가는데, 이 dfs 과정에서 기준블록도 업데이트가 필요하면 업데이트한다.
-> 그룹 내에서 기준블록은 행과 열이 가장 작은 일반블록이어야 하므로
2. 그룹을 만들어나갈 때 마다, 그룹의 정보들을 벡터에 저장한다. 그리고 이를 소팅하여 '가장 큰 그룹'을 뽑아낸다.
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int MAP[20][20];
bool VISIT[20][20];
int N, M;
int RAINBOW, TOTAL, MAX_GROUP;
int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};
vector<vector<int>> GROUPS;
int GRADE = 0;
bool hasGroup = false;
int stand_x, stand_y; // 기준블록
// 셋 다 내림차순으로
int cmp(vector<int>& a, vector<int>& b) {
if(a[0] == b[0]) {
if(a[1] == b[1]) {
return a[2] > b[2];
} else
return a[1] > b[1];
} else
return a[0] > b[0];
}
// 반시계 90도 회전
void rotate() {
int NEW_MAP[20][20];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
NEW_MAP[i][j] = MAP[j][N - i - 1];
}
}
memmove(MAP, NEW_MAP, sizeof(NEW_MAP));
}
void dfs(int x, int y, int type) {
VISIT[x][y] = true;
TOTAL++;
if(MAP[x][y] == type && (stand_x * N + stand_y > x * N + y)) {
stand_x = x; stand_y = y; // 기준블록 변경
}
if(MAP[x][y] == 0)
RAINBOW++;
for(int i = 0; i < 4; i++) {
int xx = x + mx[i];
int yy = y + my[i];
if(xx < 0 || xx >= N || yy < 0 || yy >= N)
continue;
// 0 블록(무지개블록)이거나, 같은 일반블록일때만 증가
if(!VISIT[xx][yy] && ((MAP[xx][yy] == type) || (MAP[xx][yy] == 0))) {
dfs(xx, yy, type);
}
}
}
void print() {
cout << "\n";
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cout << MAP[i][j] << " ";
}
cout << "\n";
}
}
// 내 gravity 일단 문제있으니까, 다른사람들거 찾는게 우선.
// 다른 방법으로 중력을 구현한 사람이 있나 찾아보자.
void gravity() {
// MAP에 중력 적용
// 빈 자리 = M임을 주의
// 검은 블록(-1)은 움직이지 않음을 주의
// 중력은 예전에 봤듯, 맨 아래에서부터 시작해주어야함.
for(int i = N - 2; i >= 0; i--) {
for(int j = 0; j < N; j++) {
// 내려가기
if(MAP[i][j] >= 0 && MAP[i][j] != M + 1) {
// insertion sort 사용하자.
int v = MAP[i][j];
int k;
for(k = i + 1; k < N; k++) {
if(MAP[k][j] == M + 1) {
MAP[k - 1][j] = MAP[k][j];
} else
break;
}
MAP[k - 1][j] = v;
}
}
}
}
int main() {
cin >> N >> M;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> MAP[i][j];
}
}
while(1) {
hasGroup = false;
GROUPS.clear();
for(int i = 0 ; i < N; i++) {
for(int j = 0; j < N; j++) {
if(MAP[i][j] > 0 && MAP[i][j] != M + 1) {
memset(VISIT, 0, sizeof(VISIT));
RAINBOW = TOTAL = 0;
// 블록의 종류도 인자로 넘겨줌
stand_x = i; stand_y = j; // 임시 기준블록
dfs(i, j, MAP[i][j]);
if(TOTAL >= 2) {
hasGroup = true;
// 그룹크기, 무지개블록수, 기준블록
GROUPS.push_back({TOTAL, RAINBOW, (stand_x * N + stand_y)});
}
}
}
}
if(!hasGroup)
break;
sort(GROUPS.begin(), GROUPS.end(), cmp);
// 가장 큰 블록그룹의 기준블록을 찾았으니, 한번 더 서치해서 세팅해놓음.
memset(VISIT, 0, sizeof(VISIT));
RAINBOW = TOTAL = 0;
int tx = GROUPS[0][2] / N;
int ty = GROUPS[0][2] % N;
dfs(tx, ty, MAP[tx][ty]);
GRADE += pow(TOTAL, 2);
for(int i = 0 ; i < N; i++) {
for(int j = 0; j < N; j++) {
if(VISIT[i][j])
MAP[i][j] = M + 1; // 제거된 블록은 M + 1으로 처리
}
}
// print();
gravity();
// print();
rotate();
// print();
gravity();
// print();
}
cout << GRADE << "\n";
}
중력 구현을 다른사람은 어떻게 했는지도 찾아봤는데, 어느정도 비슷한 것 같다.
그리고 나는 중력 구현에서 insertion sort와 비슷한 메커니즘을 적용했는데, 이걸 잘 정의하지 못해서 시간을 많이 잡아먹었다.
그리고 비교함수 pair같은거 내림차순 방법에 대해서는 여기 참고 글이 있다. -> https://withhamit.tistory.com/195
푸는데 약 2시간 걸렸다.
이번 문제를 풀면서 print()함수로 확실히 디버깅 계속 해줘야함을 느꼈다.
또한 다른사람들은 기준블록 어떻게 했는지도 찾아바야한다
->
찾아봤다.
다른 사람들의 풀이글에 '무지개 블록은 얼마든지 중복될 수 있으니 VISIT을 0으로 초기화해줘야한다' 라는 말들을 자주 봤는데
이게 무슨의미인고 하니, 이미 방문한 일반블록에 대해서는 어차피 한번만 방문하면 된다. 그 말은 즉슨, 2중 포문을 통해 왼쪽 상단부터 돌면서, 일반블록일 경우 dfs나 bfs를 진행하여 그룹을 만들어주고, 다시 무지개블록만 VISIT처리를 0으로 해준뒤 또다시 또다른 일반블록에 대해서 그룹을 만들어주고.. 그렇게만 하면 된다. 위의 내 풀이가 조금 불필요한 과정이 존재하긴 한다는 것을 느꼈다.
관련 풀이 : https://yabmoons.tistory.com/657
13:54 ~ 14:43
17:18 ~ 18:27
'[백준]' 카테고리의 다른 글
| 백준 17140번 C++ (0) | 2023.10.04 |
|---|---|
| 백준 11286번 절댓값 힙 (0) | 2023.08.10 |
| [BaekJoon/백준] 17144번 미세먼지 안녕! (0) | 2022.10.10 |
| [BaekJoon/백준] 23288번 주사위 굴리기 2 (0) | 2022.10.10 |
| [BaekJoon/백준] 20058번 마법사 상어와 파이어스톰 (0) | 2022.10.09 |
