코테 노트/백준

백준 21609 상어 중학교 C++

화요밍 2021. 10. 14. 18:25
728x90
반응형

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

 

21609번: 상어 중학교

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록

www.acmicpc.net

 

최종 코드

 

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

//
//  main.cpp
//  BJ21609
//
//  Created by Hwayeon on 2021/10/14.
//

#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

int N, M;
int board[20][20] = {0, };
int copy_board[20][20] = {0, };
int visit[20][20] = {0, };
int score = 0;

struct Group{
    int pr;
    int pc;
    int rainbow_blocks_cnt = 0;
    int blocks_cnt = 0;
    vector<pair<int, int>> blocks;
};
Group group;
struct cmp{
    bool operator()(Group g1, Group g2){
        if(g1.blocks_cnt == g2.blocks_cnt){
            if(g1.rainbow_blocks_cnt == g2.rainbow_blocks_cnt){
                if(g1.pr == g2.pr){
                    return g1.pc < g2.pc;
                }
                return g1.pr < g2.pr;
            }
            return g1.rainbow_blocks_cnt < g2.rainbow_blocks_cnt;
        }
        return g1.blocks_cnt < g2.blocks_cnt;
    }
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
vector<pair<int, int>> rainbow_blocks;

Group find_group(int sr, int sc){
    Group new_group;
    new_group.pr = sr;
    new_group.pc = sc;
    new_group.blocks_cnt = 1;
    new_group.blocks.push_back({sr, sc});
    queue<pair<int, int>> q;
    q.push({sr, sc});
    visit[sr][sc] = 1;
    while(!q.empty()){
        int now_r = q.front().first;
        int now_c = q.front().second;
        q.pop();
        for(int d=0; d<4; d++){
            int nr = now_r + dy[d];
            int nc = now_c + dx[d];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if(visit[nr][nc]) continue;
            if(board[nr][nc] == -1) continue;
            if(board[nr][nc] == 0){
                visit[nr][nc] = 1;
                new_group.blocks_cnt++;
                new_group.rainbow_blocks_cnt++;
                new_group.blocks.push_back({nr, nc});
                q.push({nr, nc});
            }
            else if(board[nr][nc] == board[sr][sc]){
                visit[nr][nc] = 1;
                new_group.blocks_cnt++;
                new_group.blocks.push_back({nr, nc});
                q.push({nr, nc});
            }
        }
    }
    for(int i=0; i<rainbow_blocks.size(); i++){
        visit[rainbow_blocks[i].first][rainbow_blocks[i].second] = 0;
    }
    return new_group;
}

void apply_gravity(){
    for(int c=0; c<N; c++){
        for(int r=N-1; r>=0; r--){
            if(board[r][c] == -2 || board[r][c] == -1) continue;
            for(int rr=r; rr<N-1; rr++){
                if(board[rr+1][c] != -2){
                    if(rr != r){
                        board[rr][c] = board[r][c];
                        board[r][c] = -2;
                    }
                    break;
                }
                else if(rr == N-2){
                    board[N-1][c] = board[r][c];
                    board[r][c] = -2;
                }
            }
        }
    }
}

void rotate_board(){
    memcpy(copy_board, board, sizeof(board));
    int rr = 0;
    int cc = 0;
    for(int c=N-1; c>=0; c--){
        cc = 0;
        for(int r=0; r<N; r++){
            board[rr][cc] = copy_board[r][c];
            cc++;
        }
        rr++;
    }
}

void play_auto_game(){
    while(true){
        //1. find groups
        memset(visit, 0, sizeof(visit));
        priority_queue<Group, vector<Group>, cmp> groups;
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                if(board[r][c] == -1 || board[r][c] == 0 || board[r][c] == -2) continue;
                if(visit[r][c]) continue;
                group = find_group(r, c);
                if(group.blocks_cnt >= 2) groups.push(group);
            }
        }
        if(groups.empty()) break;
        //2. erase blocks in group and get score
        group = groups.top();
        score += pow(group.blocks_cnt, 2);
        for(int i=0; i<group.blocks.size(); i++){
            board[group.blocks[i].first][group.blocks[i].second] = -2;
        }
        //3. apply gravity
        apply_gravity();
        //4. rotate 90 degrees
        rotate_board();
        //5. re-apply gravity
        apply_gravity();
        //6. update rainbow blocks location
        rainbow_blocks.clear();
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                if(board[r][c]==0){
                    rainbow_blocks.push_back({r, c});
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> board[i][j];
            if(board[i][j] == 0){
                rainbow_blocks.push_back({i, j});
            }
        }
    }
    play_auto_game();
    cout << score << endl;
    return 0;
}

풀이 과정

풀이 시간 2시간 7분

문제에 나와있는 단계별로 구현해나가면 되는 문제다.

1시간 반정도 걸려서 나름 쉽게 풀었고, 예제를 통과해서 제출을 했더니 틀렸습니다가 나왔다...

문제를 다시 읽고나서 코드를 하나씩 다시 읽어봤는데,, 왜 틀렸는지 몰랐다

결국, 게시판을 참고해보니 한번 플레이가 끝날 때마다 무지개 블록의 위치를 담는 벡터를 업데이트 해줘야 했다..!

예제의 경우는 우연하게 초기화가 안되었어도 통과했나보다...

#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

int N, M;
int board[20][20] = {0, };
int copy_board[20][20] = {0, };
int visit[20][20] = {0, };
int score = 0;

struct Group{
	//기준 블록의 위치
    int pr;
    int pc;
    //무지개 블록의 개수
    int rainbow_blocks_cnt = 0;
    //그룹 안의 블록의 개수
    int blocks_cnt = 0;
    //그룹 안의 블록의 위치들을 담는 벡터
    vector<pair<int, int>> blocks;
};
Group group;
struct cmp{
    bool operator()(Group g1, Group g2){
    	//블록 개수가 같은 경우
        if(g1.blocks_cnt == g2.blocks_cnt){
        	//무지개 블록 개수가 같은 경우
            if(g1.rainbow_blocks_cnt == g2.rainbow_blocks_cnt){
            	//행 번호가 같은 경우
                if(g1.pr == g2.pr){
                    return g1.pc < g2.pc;
                }
                return g1.pr < g2.pr;
            }
            return g1.rainbow_blocks_cnt < g2.rainbow_blocks_cnt;
        }
        return g1.blocks_cnt < g2.blocks_cnt;
    }
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
vector<pair<int, int>> rainbow_blocks;

Group find_group(int sr, int sc){
	//기준 점이 (sr, sc)인 그룹 찾기
    Group new_group;
    new_group.pr = sr;
    new_group.pc = sc;
    new_group.blocks_cnt = 1;
    new_group.blocks.push_back({sr, sc});
    queue<pair<int, int>> q;
    q.push({sr, sc});
    visit[sr][sc] = 1;
    while(!q.empty()){
        int now_r = q.front().first;
        int now_c = q.front().second;
        q.pop();
        //인접한 4방향 탐색
        for(int d=0; d<4; d++){
            int nr = now_r + dy[d];
            int nc = now_c + dx[d];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if(visit[nr][nc]) continue;
            //검정 블록인 경우, 무시한다
            if(board[nr][nc] == -1) continue;
            //무지개 블록인 경우,
            if(board[nr][nc] == 0){
                visit[nr][nc] = 1;
                new_group.blocks_cnt++;
                new_group.rainbow_blocks_cnt++;
                new_group.blocks.push_back({nr, nc});
                q.push({nr, nc});
            }
            //기준 블록과 같은 색의 블록인 경우,
            else if(board[nr][nc] == board[sr][sc]){
                visit[nr][nc] = 1;
                new_group.blocks_cnt++;
                new_group.blocks.push_back({nr, nc});
                q.push({nr, nc});
            }
        }
    }
    //무지개 블록 위치의 방문 처리를 다시 0으로 바꿔준다 -> 다른 색깔의 블록의 그룹이 될 수 있기 때문에 
    for(int i=0; i<rainbow_blocks.size(); i++){
        visit[rainbow_blocks[i].first][rainbow_blocks[i].second] = 0;
    }
    return new_group;
}

void apply_gravity(){
    for(int c=0; c<N; c++){
        for(int r=N-1; r>=0; r--){
            if(board[r][c] == -2 || board[r][c] == -1) continue;
            for(int rr=r; rr<N-1; rr++){
                if(board[rr+1][c] != -2){
                    if(rr != r){
                        board[rr][c] = board[r][c];
                        board[r][c] = -2;
                    }
                    break;
                }
                else if(rr == N-2){
                    board[N-1][c] = board[r][c];
                    board[r][c] = -2;
                }
            }
        }
    }
}

void rotate_board(){
	//중력 적용 이전의 board를 copy_board에 복사한다
    memcpy(copy_board, board, sizeof(board));
    int rr = 0;
    int cc = 0;
    for(int c=N-1; c>=0; c--){
        cc = 0;
        for(int r=0; r<N; r++){
            board[rr][cc] = copy_board[r][c];
            cc++;
        }
        rr++;
    }
}

void play_auto_game(){
    while(true){
        //1. find groups -> O(N^2)
        memset(visit, 0, sizeof(visit));
        priority_queue<Group, vector<Group>, cmp> groups;
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                if(board[r][c] == -1 || board[r][c] == 0 || board[r][c] == -2) continue;
                if(visit[r][c]) continue;
                group = find_group(r, c);
                if(group.blocks_cnt >= 2) groups.push(group);
            }
        }
        //블록 그룹이 존재하지 않는 경우, 게임을 종료한다
        if(groups.empty()) break;
        
        //2. erase blocks in group and get score -> O(N^2)
        group = groups.top();
        score += pow(group.blocks_cnt, 2);
        for(int i=0; i<group.blocks.size(); i++){
            board[group.blocks[i].first][group.blocks[i].second] = -2;
        }
        
        //3. apply gravity -> O(N^2)
        apply_gravity();
        
        //4. rotate 90 degrees -> O(N^2)
        rotate_board();
        
        //5. re-apply gravity -> O(N^2)
        apply_gravity();
        
        //6. update rainbow blocks location -> O(N^2)
        rainbow_blocks.clear();
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                if(board[r][c]==0){
                    rainbow_blocks.push_back({r, c});
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> board[i][j];
            if(board[i][j] == 0){
                rainbow_blocks.push_back({i, j});
            }
        }
    }
    play_auto_game();
    cout << score << endl;
    return 0;
}
//시간복잡도 = O(n), 공간복잡도 = O(n)

 

728x90
반응형

'코테 노트 > 백준' 카테고리의 다른 글

백준 21611 마법사 상어와 블리자드 C++  (0) 2021.10.15
백준 20056 마법사 상어와 파이어볼 C++  (0) 2021.10.14
백준 20061 모노미노도미노 2 C++  (0) 2021.10.14
백준 12015 가장 긴 증가하는 부분 수열 2 Python 3  (0) 2021.10.08
백준 14002 가장 긴 증가하는 부분 수열 4 Python 3  (0) 2021.10.06

'코테 노트/백준'의 다른글

  • 현재글백준 21609 상어 중학교 C++

관련글

댓글

티스토리툴바