반응형

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

 

17822번: 원판 돌리기

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 원판의 수를 입력받습니다.

 

2. 원판을 입력받은 대로 움직여 줍니다.

 

3. 인접한 수가 같은 경우가 있는지를 flag 변수를 통하여 체크해주고, 인접한 수가 있다면 0으로 갱신해주고, 없다면 평균보다 큰 값은 1을 빼주고, 작은 값은 1을 더해줍니다.

 

4. 위 과정을 반복한 후 원판의 모든 수를 더해 출력해줍니다.

 

[ 소스코드 ]

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
139
140
141
142
143
144
145
146
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, M, T;
int arr[51][51];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int flag = false;
int ans;
 
void average()    //평균과 비교하여 숫자 갱신
{
    int sum = 0;
    int cnt = 0;
    float avr;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] > 0) {
                sum += arr[i][j];
                cnt++;
            }
        }
    }
 
    avr = sum / (float)cnt;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] > 0) {
                if ((float)arr[i][j] > avr) {
                    arr[i][j]--;
                }
                else if ((float)arr[i][j] < avr) {
                    arr[i][j]++;
                }
            }
        }
    }
}
 
void bfs(int y, int x, int num)        //인접한 숫자 찾기
{
    queue<pair<int, int>> q;
    vector<pair<int, int>> temp;
    int visited[51][51] = { 0 };
    visited[y][x] = 1;
    q.push({ y,x });
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        temp.push_back({ y,x });    //인접한 숫자의 좌표 저장
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (xx == 0) xx = M;
            if (xx > M) xx = 1;
            if (yy > 0 && yy <= N) {
                if (visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    if (arr[yy][xx] == num) {
                        q.push({ yy,xx });
                    }
                }
            }
        }
    }
 
    if (temp.size() > 1) {    //인접한 숫자가 있다면
        for (auto next : temp) {
            int y = next.first;
            int x = next.second;
 
            arr[y][x] = 0;
            flag = true;
        }
    }
}
 
void move(int arr[51], int dir, int k) //원하는 방향으로 원판 돌리기
{
    for (int j = 0; j < k; j++) {
        if (dir == 0) {
            int temp = arr[M];
            for (int i = M; i > 1; i--) {
                arr[i] = arr[i - 1];
            }
            arr[1] = temp;
        }
        else {
            int temp = arr[1];
            for (int i = 1; i < M; i++) {
                arr[i] = arr[i + 1];
            }
            arr[M] = temp;
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < T; i++) {
        int x, d, k;
        flag = false;
        scanf("%d %d %d", &x, &d, &k);
 
        for (int j = 1; j <= N; j++) {
            if (j % x == 0) {
                move(arr[j], d, k);
            }
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] != 0) {
                    bfs(i, j, arr[i][j]);
                }
            }
        }
 
        if (!flag) {
            average();
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            ans += arr[i][j];
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17825번 - 주사위 윷놀이 (C++)  (0) 2022.09.27
[ 백준 ] 21611번 - 마법사 상어와 블리자드 (C++)  (0) 2022.09.26
[ 백준 ] 20057번 - 마법사 상어와 토네이도 (C++)  (0) 2022.09.24
[ 백준 ] 20058번 - 마법사 상어와 파이어스톰 (C++)  (0) 2022.09.23
[ 백준 ] 20056번 - 마법사 상어와 파이어볼 (C++)  (0) 2022.09.22

+ Recent posts

티스토리툴바