반응형

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

 

21609번: 상어 중학교

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받습니다.

 

2. 0, 0 좌표부터 끝까지 2중 for문을 돌려서 무지개색이 아닌 블록부터 bfs를 시작하여 연결된 블록의 좌표와 포함된 무지개색 블록의 개수를 리턴합니다.

 

3. 만약 그룹이 있다면 블록을 부숴주고, 부순 개수의 제곱만큼 포인트를 더해줍니다.

 

4. 중력을 적용시키고, 반시계 방향으로 돌린 뒤 다시 중력을 적용시킵니다.

 

5. 위 과정을 반복해 주다가 그룹이 없다면 break 해줍니다.

 

6. point를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int arr[21][21];
int temp[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int point;
 
struct status {
    vector<pair<int, int>> vect;
    int cnt;
};
 
void turn()        //반시계방향 회전
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[N - 1 - j][i] = arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
void gravity()        //중력 작용
{
    for (int i = 0; i < N; i++) {
        for (int j = N - 2; j >= 0; j--) {
            if (arr[j][i] >= 0 && arr[j + 1][i] == -2) {
                arr[j + 1][i] = arr[j][i];
                arr[j][i] = -2;
                j += 2;
            }
        }
    }
}
 
status bfs(int cury, int curx, int num)    //같은 색과 무지개 색의 블록 좌표, 무지개 색 블록 개수 return
{
    queue<pair<int, int>> q;
    vector<pair<int, int>> vect;
    q.push({ cury,curx });
    vect.push_back({ cury,curx });
    int visited[21][21] = { 0 };
    visited[cury][curx] = 1;
    int cnt = 0;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy<N && xx>=0 && xx < N) {
                if ((arr[yy][xx] == 0 || arr[yy][xx] == num) && !visited[yy][xx]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                    vect.push_back({ yy,xx });
                    if (arr[yy][xx] == 0) {
                        cnt++;
                    }
                    else {
                        temp[yy][xx] = 1;
                    }
                }
            }
        }
    }
 
    return { vect,cnt };
}
 
int main()
{
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
 
    while (1) {
        memset(temp, 0, sizeof(temp));
        status ans;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (temp[i][j] == 0 && arr[i][j] > 0) {
                    status temp = bfs(i, j, arr[i][j]);
 
                    if (ans.vect.size() < temp.vect.size()) {
                        ans = temp;
                    }
                    else if (ans.vect.size() == temp.vect.size()) {
                        if (ans.cnt <= temp.cnt) {
                            ans = temp;
                        }
                    }
                }
            }
        }
 
        for (auto next : ans.vect) {
            int y = next.first;
            int x = next.second;
            arr[y][x] = -2;
        }
 
        int size = ans.vect.size();
 
        if (size <= 1) {
            printf("%d", point);
            return 0;
        }
 
        point += size * size;
 
        gravity();
 
        turn();
 
        gravity();
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29

+ Recent posts

티스토리툴바