[๋ฐฑ์ค€/C++] 21610๋ฒˆ ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ๋น„๋ฐ”๋ผ๊ธฐ

2022. 10. 6. 23:36ยทPS/C++
728x90

๋ฐฑ์ค€

 


๐Ÿค”๋ฌธ์ œ ์ดํ•ด

๊ทธ๋ƒฅ ๋‹จ์ˆœ ๊ตฌํ˜„ ๋ฌธ์ œ๋กœ ์ž˜ ์ฝ๊ณ  ์กฐ๊ฑด์— ๋งž์ถฐ ๋น„๊ตฌ๋ฆ„์„ ์˜ฎ๊ฒจ์ฃผ๋ฉด ๋˜๋Š” ๋ฌธ์ œ์˜€๋‹ค. 


๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ

(i, j)์— ์œ„์น˜ํ•œ ๋ฐ”๊ตฌ๋‹ˆ์— ๋‹ด๊ธด ๋ฌผ์˜ ์–‘์„ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฐ์—ด map[i][j]

๋ช…๋ น ๊ณผ์ • 3๋ฒˆ์—์„œ ์‚ฌ๋ผ์ง„ ๊ตฌ๋ฆ„์„ ํ‘œ์‹œํ•˜๋Š” ๋ฐฐ์—ด visited[i][j]

๋ช…๋ น์—์„œ ์ฃผ๋Š” ๋ฐฉํ–ฅ์„ ์˜๋ฏธํ•˜๋Š” di[k]์™€ dj[k]

๊ฑฐ๋ฆฌ๊ฐ€ 1์ธ ๋Œ€๊ฐ์„ ์„ ์˜๋ฏธํ•˜๋Š” diag_i[k]์™€ diag_j[k]

๊ตฌ๋ฆ„์˜ ์œ„์น˜๋ฅผ ์ €์žฅํ•  ํ cloud

 

m๋ฒˆ์˜ ๋ช…๋ น๋งˆ๋‹ค ์•„๋ž˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•ด์ค€๋‹ค.

1. cloud์˜ front ๋น„๊ตฌ๋ฆ„์˜ ์œ„์น˜์— ๋ฐฉํ–ฅ * ๊ฑฐ๋ฆฌ๊ฐ’์„ ๋”ํ•ด์ฃผ๊ณ  ๊ฒฉ์žํฌ๊ธฐ(N)๋งŒํผ ๋‚˜๋จธ์ง€ ์—ฐ์‚ฐ

2. ๊ณ„์‚ฐ๋œ ์œ„์น˜๊ฐ’์ด ์Œ์ˆ˜์ด๊ฑฐ๋‚˜ 0์ด๋ฉด +N

3. popํ•ด์ฃผ๊ณ  ๊ณ„์‚ฐ๋œ ์œ„์น˜๊ฐ’์˜ ๋น„์˜ ์–‘์„ +1ํ•˜๊ณ  ์œ„์น˜๊ฐ’์„ cloud์— push

4. ์˜ฎ๊ฒจ์ง„ ๋น„๊ตฌ๋ฆ„์— ๋Œ€ํ•ด ๋Œ€๊ฐ์„  ๊ฑฐ๋ฆฌ1์— ๋ฌผ์ด ์žˆ๋Š” ๋ฐ”๊ตฌ๋‹ˆ์˜ ๊ฐœ์ˆ˜๋งŒํผ ๋น„๊ตฌ๋ฆ„์ด ์œ„์น˜ํ•œ ๋ฐ”๊ตฌ๋‹ˆ์— ๋ฌผ ์ถ”๊ฐ€

5. ๋ฌธ์ œ์˜ ๋ช…๋ น ๊ณผ์ • 3๋ฒˆ์—์„œ ์‚ฌ๋ผ์ง„ ๊ตฌ๋ฆ„์ž„์„ visited์— ํ‘œ์‹œ

6. ๋ชจ๋“  ๋ฐ”๊ตฌ๋‹ˆ๋ฅผ ๋Œ๋ฉด์„œ ๋ช…๋ น ๊ณผ์ • 3๋ฒˆ์—์„œ ์‚ฌ๋ผ์ง„ ๊ตฌ๋ฆ„์ด ์•„๋‹ˆ๋ฉด์„œ ๋ฐ”๊ตฌ๋‹ˆ์— ๋ฌผ์ด 2์ด์ƒ ์žˆ๋Š” ๊ณณ์˜ ์œ„์น˜๋ฅผ cloud์— ์ถ”๊ฐ€ํ•˜๊ณ  ๋ฐ”๊ตฌ๋‹ˆ์—์„œ ๋ฌผ 2 ๋บŒ

7. visited ์ดˆ๊ธฐํ™”

 

๋งˆ์ง€๋ง‰์—” map์˜ ๋ชจ๋“  ๊ฐ’์„ ๋‹ค ๋”ํ•ด ์ถœ๋ ฅํ•ด์ค€๋‹ค.


#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n, m, r, c, d, s;
int map[51][51];
bool visited[51][51];
int di[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dj[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int diag_i[4] = {-1, -1, 1, 1};
int diag_j[4] = {-1, 1, -1, 1};
queue<pair<int, int>> cloud;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }

    cloud.push({n, 1});
    cloud.push({n, 2});
    cloud.push({n - 1, 1});
    cloud.push({n - 1, 2});

    for (int i = 0; i < m; i++) {
        cin >> d >> s;
        int size = cloud.size();
        for (int j = 0; j < size; j++) {
            r = (cloud.front().first + di[d] * s) % n;
            c = (cloud.front().second + dj[d] * s) % n;
            if (r <= 0) {
                r += n;
            }
            if (c <= 0) {
                c += n;
            }
            cloud.pop();
            cloud.push({r, c});
            map[r][c]++;
        }
        while (!cloud.empty()) {
            int cnt = 0;
            r = cloud.front().first;
            c = cloud.front().second;
            cloud.pop();
            for (int k = 0; k < 4; k++) {
                int mr = r + diag_i[k];
                int mc = c + diag_j[k];
                if (mr <= 0 || mc <= 0 || mr > n || mc > n) continue;
                if (map[mr][mc] > 0)
                    cnt++;
            }
            visited[r][c] = true;
            map[r][c] += cnt;
        }
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (map[j][k] >= 2 && !visited[j][k]) {
                    cloud.push({j, k});
                    map[j][k] -= 2;
                }
            }
        }
        memset(visited, false, sizeof(visited));
    }
    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            total += map[i][j];
        }
    }
    cout << total;
}

 

728x90

'PS > C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€/C++] 17404๋ฒˆ RGB๊ฑฐ๋ฆฌ 2  (0) 2022.11.02
[๋ฐฑ์ค€/C++] 4889๋ฒˆ ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด  (0) 2022.10.27
[๋ฐฑ์ค€/C++] 24524๋ฒˆ ์•„๋ฆ„๋‹ค์šด ๋ฌธ์ž์—ด  (0) 2022.10.05
[๋ฐฑ์ค€/C++] 9663๋ฒˆ N-Queen  (0) 2022.08.16
[๋ฐฑ์ค€/C++] 16457๋ฒˆ ๋‹จํ’์žŽ ์ด์•ผ๊ธฐ  (0) 2022.08.12
'PS/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€/C++] 17404๋ฒˆ RGB๊ฑฐ๋ฆฌ 2
  • [๋ฐฑ์ค€/C++] 4889๋ฒˆ ์•ˆ์ •์ ์ธ ๋ฌธ์ž์—ด
  • [๋ฐฑ์ค€/C++] 24524๋ฒˆ ์•„๋ฆ„๋‹ค์šด ๋ฌธ์ž์—ด
  • [๋ฐฑ์ค€/C++] 9663๋ฒˆ N-Queen
yulee_to
yulee_to
  • yulee_to
    yulee
    yulee_to
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (121)
      • CS (2)
        • OS (0)
        • DB (0)
        • Network (2)
      • Develop (21)
        • Spring (9)
        • Java (12)
        • Python (0)
        • Algorithm (0)
        • ๊ธฐํƒ€ (0)
      • PS (39)
        • C++ (39)
        • Java (0)
      • TIL (14)
      • Book (39)
        • ์ž๋ฐ”์˜ ์‹  (32)
        • ์Šคํ”„๋ง ์ž…๋ฌธ์„ ์œ„ํ•œ ์ž๋ฐ” ๊ฐ์ฒด ์ง€ํ–ฅ์˜ ์›๋ฆฌ์™€ ์ดํ•ด (7)
      • ETC (4)
        • Blog (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ๋ฉ€ํ‹ฐ์บ ํผ์Šคit๋ถ€ํŠธ์บ ํ”„
    Java
    C++
    ์—์Šค๋„ท์‹œ์Šคํ…œ ๋ถ€ํŠธ์บ ํ”„
    ๋ฐฑ์ค€
    boj
    ํด๋ผ์šฐ๋“œ ํ™œ์šฉ ๋„คํŠธ์›Œํฌ ์—”์ง€๋‹ˆ์–ด ๋ถ€ํŠธ์บ ํ”„
    ๊ฐ์ฒด์ง€ํ–ฅ
    GodOfJava
    EC2
    ๋ฌธ์ œํ’€์ด
    ์—์Šค๋„ท์‹œ์Šคํ…œ
    TiL
    ์ž๋ฐ”์˜ ์‹ 
    ์Šคํ„ฐ๋””
    ์Šคํ”„๋ง ์ž…๋ฌธ
    1์ผ1๋ฐฑ์ค€
    ๋ถ€ํŠธ์บ ํ”„ํ›„๊ธฐ
    ์ž๋ฐ”
    ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
yulee_to
[๋ฐฑ์ค€/C++] 21610๋ฒˆ ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ๋น„๋ฐ”๋ผ๊ธฐ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”