https://www.acmicpc.net/problem/21609
2021년 삼성 코딩테스트 2번 문제였다.
정말 호흡이 길었던 빡센 구현 문제여서 풀었을 때 도파민이 엄청났다..
문제 및 입출력
중간 그림은 생략하였다.
정보량이 정말 많아서 세심하게 정리하지 않으면 뻘짓으로 가득해지는 문제다.
문제에서 추출할 수 있는 정보는 다음과 같다.
- 특정 블록의 상하좌우 블록을 인접한 블록이라고 한다.
- 블록 그룹은 적어도 하나의 일반 블록(1~M번)이 존재해야 하고, 적어도 2개 이상의 블록으로 구성되어야 하며, 그룹 내부 일반 블록의 색은 모두 같아야 한다.
- 그룹 내에선 어떤 그룹 구성 블록으로 이동할 수 있어야 한다.
- -1은 검은 블록, 0은 무지개 블록이다.
- 비어있는 블록임을 표현할 번호가 필요하다. (-2로 처리)
- 무지개 블록은 어떤 그룹 블록이든 포함될 수 있다.
- 블록 그룹은 기준 블록을 가지며, 기준 블록은 무지개색이 아니다.
- 우선순위가 가장 높은 블록 그룹을 찾아 제거하고 그룹의 크기^2를 계산한다.
- 우선순위는 크기 내림차순, 무지개 개수 내림차순, 기준블록 행-열 오름차순이다.
- 제거 후 중력으로 인해 블록들이 바닥(마지막 행 방향)으로 떨어진다.
- 검은 블록은 중력이 적용되지 않으며, 일종의 받침대 역할을 수행한다.
- 회전을 통해 전체 블록이 90도 반시계로 회전한다.
- 회전 후 다시 중력이 적용된다.
- 이 사이클이 종료 전까지 반복된다.
- 종료조건: 블록 그룹이 아예 없거나, 현재 사이클에 크기가 2 이상인 블록 그룹이 존재하지 않는 경우
이 모든 정보를 쥐고 해결 과정으로 들어가야 한다.
거의 비문학 수준이다,,
해결 과정
문제에서 제시한 대로 오토플레이를 구성하는 하나의 Cycle는 다음과 같다.
- 각 그룹 블록별 BFS
- BFS의 결과로 생성된 그룹 블록 중 가장 우선순위가 높은 블록 선택
- 해당 블록을 제거하고 블록의 크기^2 계산
- 중력 적용
- 90도 반시계 회전
- 중력 적용
BFS, 우선순위 산출, 블록 그룹 제거, 중력, 회전
크게 6가지로 과정을 분리해서 하나씩 구현하였다.
BFS
우선순위 산출에 활용하기 위해 그룹 크기와 무지개블록 개수를 반환하도록 했다.
pair<int, int> bfs(int sx, int sy){
queue<pair<int, int> > q;
visited[sx][sy] = true;
q.push(make_pair(sx, sy));
int cnt = 1;
int rainbow = 0;
int color = map[sx][sy];
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(visited[nx][ny] || map[nx][ny] == -1) continue;
if(map[nx][ny] == 0 || map[nx][ny] == color){
if(map[nx][ny] == 0) rainbow++;
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
cnt++;
}
}
}
return make_pair(cnt, rainbow); // 그룹 크기, 무지개 개수
}참고로 매 BFS 전 모든 무지개 블록의 방문 여부를 다시 False로 초기화주어야 한다.
무지개 블록은 모든 그룹이 사용할 수 있는 공공재이기에, 앞 그룹이 사용했다는 이유로 바로 뒷 그룹이 사용하지 못하는 불상사가 발생할 수 있기 때문이다.
이 문제를 파악하는 게 중력 구현과 더불어 가장 오랜 시간이 걸렸다.
우선순위 산출
bool cmp(pair<pair<int, int>, pair<int, int> > p1, pair<pair<int, int>, pair<int, int> > p2){ // 문제 요구에 따른 정렬
if(p1.first.first == p2.first.first){
if(p1.first.second == p2.first.second){
if(p1.second.first == p2.second.first){
return p1.second.second > p2.second.second;
}
return p1.second.first > p2.second.first;
}
return p1.first.second > p2.first.second;
}
return p1.first.first > p2.first.first;
}2쌍의 pair로 구성된 벡터를 통해 (그룹크기, 그룹 내 무지개 개수, 기준블록 행번호, 기준블록 열번호)를 바탕으로 정렬을 수행하여 가장 우선순위가 높은 블록 그룹을 선택 및 제거하였다.
블록 그룹 제거
이 그룹에 속한 모든 블록을 다 치우고 빈 블록으로 채워야 하기 때문에 이 역시 BFS가 필요했다. 빈 블록은 -2로 표현하였다. (0이 무지개블록이므로)
int deleteblock(int sx, int sy){
memset(visited, false, sizeof(visited));
queue<pair<int, int> > q;
visited[sx][sy] = true;
q.push(make_pair(sx, sy));
int cnt = 1;
int color = map[sx][sy];
copys[sx][sy] = -2; // 빈 블록
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(visited[nx][ny] || map[nx][ny] == -1) continue;
if(map[nx][ny] == 0 || map[nx][ny] == color){
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
copys[nx][ny] = -2;
cnt++;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = copys[i][j]; // 빈 블록 업데이트
}
}
return cnt*cnt;
}참고로 복사본 배열을 사용하지 않고 바로바로 좌표를 빈 블록 -2로 수정하면 다음 연산이 이 영향을 받아 잘못된 결과가 나타난다.
이해하기 어려우면 이 문제를 먼저 풀고 오는 것을 권한다.
중력
무지개 블록 이슈와 더불어 사실상 이 문제의 승부처였다.
회전도 아닌 중력..이라는 낯선 연산을 -1이라는 받침대(?)와 함께 구현해야 했다.
바닥으로부터 위로 올라오며 받침대인지, 빈 공간인지, 블록인지를 판정한 후,
- 빈 공간(-2) -> 아무 일 없음
- 받침대(-1) -> 빈 공간이 나오기 전까지 계속 바닥 상승,
만약 인덱스가 지붕(0)을 뚫으면 해당 열은 중력 연산 종료 - 블록(0~M) -> 블록과 현재 바닥을 의미하는 빈 블록을 Swap하고 바닥 한칸 상승
void gravity(){ // 중력
for(int j=0; j<n; j++){
int nextf = n-1; // 바닥 설정
for(int i=n-1; i>=0; i--){
if(map[i][j] == -2) { // 빈공간 -> 아무일도 없음
continue;
} else if(map[i][j] == -1){ // 받침대
nextf = i;
while(map[nextf][j] != -2) { // 빈공간 나오기 전까지 쭉 올라감
nextf--;
if(nextf < 0){ // 지붕 뚫을 시 종료
i = -1;
break;
}
}
i = nextf; // 받침대 위 어딘가의 새로운 바닥 정의
} else {
swap(map[nextf][j], map[i][j]); // 블록이 바닥으로 이동
nextf--; // 바닥 1칸 상승
}
}
}
}Swap을 해도 되는가? 라는 고민이 있었지만, 받침대를 감지할 시 바닥을 재정의하는 부분 덕분에 문제 없이 처리가 가능하다.
회전
void rotate(){ // 90도 반시계 회전
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
copys[i][j] = map[j][n-1-i];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = copys[i][j];
}
}
}복사본 배열을 통해 회전을 구현한 후 원본 배열에 반영하였다.
소스 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
int copys[401][401]; // 복사본
int map[401][401]; // -2는 공백, -1은 검정, 0은 무지개
bool visited[401][401];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void input(){ // 입력
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> map[i][j];
}
}
}
void makecopy(){ // 복사본 배열 초기화
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
copys[i][j] = map[i][j];
}
}
}
bool cmp(pair<pair<int, int>, pair<int, int> > p1, pair<pair<int, int>, pair<int, int> > p2){ // 문제 요구에 따른 정렬
if(p1.first.first == p2.first.first){
if(p1.first.second == p2.first.second){
if(p1.second.first == p2.second.first){
return p1.second.second > p2.second.second;
}
return p1.second.first > p2.second.first;
}
return p1.first.second > p2.first.second;
}
return p1.first.first > p2.first.first;
}
pair<int, int> bfs(int sx, int sy){
queue<pair<int, int> > q;
visited[sx][sy] = true;
q.push(make_pair(sx, sy));
int cnt = 1;
int rainbow = 0;
int color = map[sx][sy];
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(visited[nx][ny] || map[nx][ny] == -1) continue;
if(map[nx][ny] == 0 || map[nx][ny] == color){
if(map[nx][ny] == 0) rainbow++;
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
cnt++;
}
}
}
return make_pair(cnt, rainbow); // 그룹 크기, 무지개 개수
}
int deleteblock(int sx, int sy){
memset(visited, false, sizeof(visited));
queue<pair<int, int> > q;
visited[sx][sy] = true;
q.push(make_pair(sx, sy));
int cnt = 1;
int color = map[sx][sy];
copys[sx][sy] = -2; // 빈 블록
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(visited[nx][ny] || map[nx][ny] == -1) continue;
if(map[nx][ny] == 0 || map[nx][ny] == color){
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
copys[nx][ny] = -2;
cnt++;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = copys[i][j]; // 빈 블록 업데이트
}
}
return cnt*cnt;
}
void gravity(){ // 중력
for(int j=0; j<n; j++){
int nextf = n-1; // 바닥
for(int i=n-1; i>=0; i--){
if(map[i][j] == -2) {
continue;
} else if(map[i][j] == -1){
nextf = i;
while(map[nextf][j] != -2) {
nextf--;
if(nextf < 0){
i = -1;
break;
}
}
i = nextf;
} else {
swap(map[nextf][j], map[i][j]);
nextf--;
}
}
}
}
void rotate(){ // 90도 반시계 회전
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
copys[i][j] = map[j][n-1-i];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = copys[i][j];
}
}
}
void zeroreset(){ // 무지개 블록은 모든 그룹들이 쓸 수 있어야 하므로 매 탐색마다 초기화해줘야함
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(visited[i][j] && map[i][j] == 0) visited[i][j] = false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
int answer = 0;
while(1){
memset(visited, false, sizeof(visited));
makecopy();
vector<pair<pair<int, int>, pair<int, int> > > v;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!visited[i][j] && map[i][j] >= 1){
pair<int, int> blocks = bfs(i, j);
v.push_back(make_pair(blocks, make_pair(i, j)));
zeroreset();
}
}
}
if(v.empty()) break; // 비었으면 종료
sort(v.begin(), v.end(), cmp);
if(v[0].first.first < 2) break; // 젤 큰 그룹 크기가 2 미만이면 종료
answer += deleteblock(v[0].second.first, v[0].second.second);
gravity(); // 중력
rotate(); // 90도 반시계 회전
gravity(); // 중력
}
cout << answer;
return 0;
}교훈
- 코드를 치기 전에 내가 놓치면 안 되는 정보를 미리 정리해두고 시작하자. 숨겨진 정보로 인해 시간을 너무 낭비했다.
- 2차원 배열을 활용한 회전 등의 변칙적인 연산은 여러 문제로 익숙해져야 실전에서 빠르게 처리할 수 있다.
Discover Tomorrow