[백준 21609][C++] 상어 중학교

문제

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

21609번: 상어 중학교

 

풀이 과정

1. 회전 함수 구현

2. 중력 함수 구현

3. 탐색을 통해 가장 큰 블록을 찾는 함수 구현

    블록 수 같은 경우 무지개 블록 확인

    무지개 블록 수 같으면 기준 블록 확인

4. 블록 찾아서 제거, 중력, 회전, 중력 순으로 수행되는 하나의 사이클 생성

5. 만약 찾은 최대 블록의 수가 1개 이하라면 그룹이 없는 것이므로 종료하며 현재까지 점수의 합 출력

 

 

세부 풀이

(1) rotate 함수

[문제 20058]의 rotate 함수 구현을 바탕으로 작성했다. 해당 링크의 문제와는 반대 방향으로 회전시키는 것을 고려하여 구현했다.

 

(2) gravity 함수

하나의 열을 기준으로 vector를 이용하여 빈칸이 아닌 값들을 모두 넣는다. 넣으며 map을 빈칸으로 초기화한다.

벡터에 들어있는 값을 idx = N-1부터 시작하여 map [idx][j]에 넣어준다.

이때 벡터에서 꺼낸 값이 -1이라면 -1이 있던 row로 idx를 바로 이동한다. (왜냐하면 -1은 중력의 영향을 받지 않기 때문이다.)

 

아래에 예시를 첨부하였다.

 

ROW	최초 모양 (map)	최종 모양 (map)
0	-1	-1
1	1	0
2	3	1
3	0	3
4	-1 (row 값 : 4)	-1
5	0	0

 

벡터에는 {-1,4} {3,2} {1,1} {-1,0} 값이 들어있게 된다.

탐색은 벡터의 인자를 모두 탐색한다.

 

벡터 0번 인자  (현재 idx = 5)

벡터의 인자를 확인한다. -1의 값을 가진다.

idx를 인자에 저장되어있는 row의 값으로 변경하고 (idx=4) map [idx][j]에 -1을 저장한다.

idx -- 를 통해 다음 위치로 idx를 이동시킨다.

 

벡터 1번 인자  (현재 idx = 3)

벡터의 인자를 확인한다. 3의 값을 가진다.

map [idx][j]에 3을 저장한다.

idx -- 를 통해 다음 위치로 idx를 이동시킨다.

 

벡터 2번 인자  (현재 idx = 2)

벡터의 인자를 확인한다. 1의 값을 가진다.

map [idx][j]에 1을 저장한다.

idx -- 를 통해 다음 위치로 idx를 이동시킨다.

 

벡터 3번 인자  (현재 idx = 1)

벡터의 인자를 확인한다. -1의 값을 가진다.

idx를 인자에 저장되어있는 row의 값으로 변경하고 (idx=0) map [idx][j]에 -1을 저장한다.

idx -- 를 통해 다음 위치로 idx를 이동시킨다.

 

(3) (4) bfs 함수 + one_cycle 함수

이 문제의 핵심이라고 생각되는 주의해야 할 점이 두 가지 있었다.

첫 번째 : 무지개 블록은 모든 블록이 이용할 수 있으므로 한 번의 탐색 이후 다시 방문할 수 있도록 처리해야 한다. visited = false로 초기화

두 번째 : 블록 수가 같다면 무지개 블록 수 비교, 무지개 블록 수 같다면 기준 블록 비교하는 조건을 만족하도록 탐색을 진행해야 한다.

 

첫 번째는 초기화의 영역이라 생각보다 빨리 찾아냈는데, 두 번째를 만족시키는 것이 생각보다 조건이 많아서 까다로웠다.

 

이후 위 두 조건을 만족하며 bfs를 통해 최대 값을 찾아 점수에 추가해주었다.

 

아래의 반례들을 수행하면서 틀린 부분을 찾아 수정하며 작성했다.

[참고한 반례 링크 : 1]  [참고한 반례 링크 : 2]

 

(5) solve 함수

one_cycle 함수를 while 문을 통해 반복시키며 남은 블록의 그룹이 없다면 현재까지의 점수를 출력하는 함수

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

//빈칸을 0으로 나타내기 위해
//검은색 블록은 -1, 무지개 블록은 -2 로 표현
const int max_n = 22;
int map[max_n][max_n];
bool visited[max_n][max_n];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int N,M, ans;
struct value_row{
    int value,row;
};

void Input(){
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
            if(map[i][j]==0) map[i][j]=-2;
        }
    }
}

void rotate() {
	int temp[max_n][max_n];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			temp[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = temp[j][N-1-i];
		}
	}
}

void gravity(){
    for(int j=0;j<N;j++){
        vector<value_row> v;
        for(int i=N-1; i>=0; i--){
            if(map[i][j]!=0){
                v.push_back({map[i][j],i});
            }
            map[i][j]=0;
        }
        int idx = N-1;
        for(int i=0; i<v.size(); i++){
            if(v[i].value == -1){
                idx = v[i].row;
                map[idx][j]=v[i].value;
                idx--;
            }
            else{
                map[idx][j]=v[i].value;
                idx--;
            }
        }
    }
}

int bfs(int ix, int iy, int& num_rainbow){
    visited[ix][iy]=true;
    int value = map[ix][iy];
    int ret=1;
    map[ix][iy]=0;
    queue<pair<int,int>> q;
    q.push({ix,iy});
    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+dir[i][0];
            int ny = y+dir[i][1];
            if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
            if(visited[nx][ny] || map[nx][ny]==-1) continue;
            if(map[nx][ny]==value || map[nx][ny]==-2){
                if(map[nx][ny]==-2) num_rainbow++;
                ret++;
                map[nx][ny] = 0;
                visited[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
    return ret;
}


bool one_cycle(){
    int max_num_rainbow = -1;
    int max_num=0;
    int tx=0, ty=0;
    int copy_map[max_n][max_n];
    int num_rainbow;
    //무지개 좌표 저장
    vector<pair<int,int>> rainbow_v;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            copy_map[i][j] = map[i][j];
            if(map[i][j]==-2) rainbow_v.push_back({i,j});
        }
    }
    //방문 노드 초기화
    memset(visited, false, sizeof(visited));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            //무지개 좌표들에 대해서 visited와 map 복구 (다른 그룹에서도 방문할 수 있도록)
            for(int k=0;k<rainbow_v.size();k++){
                visited[rainbow_v[k].first][rainbow_v[k].second] = false;
                map[rainbow_v[k].first][rainbow_v[k].second]= -2;
            }
            //현재 좌표가 이미 검정, 빈칸, 방문 된 칸 이라면 continue
            //시작 좌표는 무지개가 될 수 없다. (그룹엔 최소 하나의 색깔 블록있어야함)
            if(map[i][j]==-1 || map[i][j] == 0 || visited[i][j] || map[i][j]==-2) continue;
            num_rainbow=0;
            int cur_num = bfs(i,j,num_rainbow);
            if(max_num<cur_num){
                tx=i; ty=j; 
                max_num_rainbow = num_rainbow;
                max_num = cur_num;
            }
            if(max_num==cur_num){
                if(max_num_rainbow<=num_rainbow){
                    tx=i; ty=j;
                    max_num_rainbow = num_rainbow;
                }
            }
        }
    }

    if(max_num<=1) return false;

    memset(visited, false, sizeof(visited));
    memcpy(map, copy_map, sizeof(map));
    bfs(tx,ty,num_rainbow);

    ans+=max_num*max_num;

    gravity();
    rotate();
    gravity();

    return true;
}

void solve(){
    while(one_cycle()){
    }
    cout << ans;
    return;
}

int main(){
    Input();
    solve();
    return 0;
}

 

결과 및 후기

오전의 일정 때문에 저녁을 먹고 해당 문제 풀이를 수행했는데, 생각보다 시간이 많이 소모되었다. 조건이 몇 개 더 추가되는 만큼 고려해야 할 사항도 많아지고 틀릴 수 있는 부분도 많아지기 때문에 더 섬세하고 꼼꼼한 풀이가 필요했다.