백준 17822 원판돌리기

작성일 | In |

Problem : 원판 돌리기

유형 : 구현

문제 해석

  • 원판을 돌린다.
  • 인접한 것을 삭제한다.
  • 인접한 것이 없다면 삭제하지 않고 평균을 구한다.
  • 평균에 맞춰서 조건에 맞춰 증감 연산을 진행한다.

문제 재해석

  • 단순 구현 문제이다.
  • 해석한 그대로 구현 하면 된다

해결 전략

  • 범위가 좁으므로, 따로 전략 없이 시키는 대로 구현하면 된다.
  • 원판의 모양은 배열로 표시할 수 있다.
    • 행은 원판의 번호
    • 열은 원판 내 번호의 위치

설계(30), 구현 (70)

  • 원판을 돌리는 것은 rotate 함수를 이용했다.
    • 이를 위해 입력받을때 vector에 보관했다.
  • 인접한 것을 확인하는 것은 4방면 탐색을 통해 확인한다.
  • 인접해서 지워질 숫자는 visit 배열에 표시해둔다.
  • 지워진 것이 하나도 없다면 평균을 구하고, 증감 연산을 진행한다.

주의할 점

  • 2번 4번을 돌린다면, 인덱스는 0번 3번을 돌려야 한다.
  • 배수에 해당하는 원판을 전부 다 돌린 후에 삭제나 평균값 비교 작업이 들어가야 한다.
  • 평균은 정수가 아닌 실수로 계산한다.
  • 처음부터 인접한 숫자가 주어진 원판이 입력으로 들어올 수 있다.


image

  • 원판 내 숫자가 총 4개일때 0번 인덱스와 3번인덱스가 인접 할 수 있다.


image

  • 인접하는 것들을 바로 지워버리면 안된다.
  • 3번이 2번과 인접하여 지웠는데 1번과 2번도 인접해 있다면 1번은 지워져야 하지만 지워질 수 없게 된다.

코드

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
147
148
149
150
151
152
153
#include <bits/stdc++.h>

using namespace std;

int n, m, t;

vector<int> board[52];
bool visit[52][52];

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };


void delete_num() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (visit[i][ii]) board[i][ii] = 0;
        }
    }
}

int get_sum() {
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            sum += board[i][ii];
        }
    }

    return sum;
}

double get_avg() {
    double sum = 0;
    int cnt = 0;

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (board[i][ii] == 0)continue;
            sum += board[i][ii];
            cnt++;
        }
    }

    return sum / cnt;
}

void average_set() {

    double avg = get_avg();

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (board[i][ii] == 0)continue;
            if (board[i][ii] < avg) board[i][ii]++;
            else if (board[i][ii] > avg) board[i][ii]--;
        }
    }
}

bool delete_check() {

    bool _delete = false;
    memset(visit, false, sizeof(visit));

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {

            if (board[i][ii] == 0)continue;

            bool deleted = false;
            
            for (int dir = 0; dir < 4; ++dir) {
                int nx = i + dx[dir];
                int ny = ii + dy[dir];

                if (nx < 0 or nx >= n)continue;
                if (ny < 0) ny += m;
                if (ny >= m) ny %= m;

                if (board[nx][ny] == 0)continue;
                if (board[nx][ny] == board[i][ii]) {
                    deleted = true;
                    visit[nx][ny] = true;
                }
            }
            if (deleted) {
                _delete = true;
                visit[i][ii] = true;
            }
        }
    }

    if (_delete) delete_num();

    return _delete;
}

void rotate(int k, int rotate_dir, int rotate_cnt) {
    
    int cnt = rotate_cnt % m;
    if (rotate_dir == 0) {
        rotate(board[k].rbegin(), board[k].rbegin() + cnt, board[k].rend());
    }
    else {
        rotate(board[k].begin(), board[k].begin() + cnt, board[k].end());
    }
}

void solve() {

    int a, rotate_dir, rotate_cnt;

    while (t--) {
        cin >> a >> rotate_dir >> rotate_cnt;

        int round_num = 0;
        while (1) {
            round_num += a;
            if (round_num - 1 >= n)  break;
            rotate(round_num - 1, rotate_dir, rotate_cnt);
        }

        if (!delete_check()) average_set();
    }

    cout << get_sum() << "\n";
}

void input() {
    cin >> n >> m >> t;

    int num;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            cin >> num;
            board[i].push_back(num);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

  • 문제 이해를 한번에 제대로 못했다.
  • 주의할 점에서 나열한 부분 중 대부분을 처음 설계할 때 놓쳤었다.
  • 이 때문에 구현 도중 수정이 잦았고, 구현 시간이 굉장히 길어졌었다.
  • 입력부분에서 처음에 vector에 넣어야하는데 배열처럼 넣는 실수를 했다.