[๋ฐฑ์ค€] 1992 ์ฟผ๋“œํŠธ๋ฆฌ - ์žฌ๊ท€ํ•จ์ˆ˜

2024. 8. 19. 04:15ยท๐Ÿ’ป Algorithms/๋ฐฑ์ค€

[ ๋ฌธ์ œ๋งํฌ ]

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

 

๐Ÿšฉ ์กฐ๊ฑด

  1. 0,1๋กœ๋งŒ ๊ตฌ์„ฑ๋œ ์˜์ƒ์„ ์••์ถ•ํ•ด๋ผ. ๋ชจ๋‘ 0์œผ๋กœ๋งŒ ๋˜์–ด ์žˆ์œผ๋ฉด ์••์ถ• ๊ฒฐ๊ณผ๋Š” "0". ๋ชจ๋‘ 1๋กœ๋งŒ ๋˜์–ด ์žˆ์œผ๋ฉด ์••์ถ• ๊ฒฐ๊ณผ๋Š” "1".
  2. ์„ž์—ฌ ์žˆ์œผ๋ฉด ์™ผ์ชฝ ์œ„, ์˜ค๋ฅธ์ชฝ ์œ„, ์™ผ์ชฝ ์•„๋ž˜, ์˜ค๋ฅธ์ชฝ ์•„๋ž˜, ์ด๋ ‡๊ฒŒ 4๊ฐœ์˜ ์˜์ƒ์œผ๋กœ ๋‚˜๋ˆ„์–ด ์••์ถ•ํ•˜๊ณ , ๊ฒฐ๊ณผ๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ๊ด„ํ˜ธ ์•ˆ์— ๋ฌถ์–ด์„œ ํ‘œํ˜„
  3. NxN ํฌ๊ธฐ์˜ ์˜์ƒ์ด ์ฃผ์–ด์ง€๊ณ , 1<=N<=64

์˜ˆ์‹œ) ์–˜์˜ ์ถœ๋ ฅ ๊ฒฐ๊ณผ๋Š” "(0(0011)(0(0111)01)1)"

 

 

๐Ÿšฉ ์ ‘๊ทผ

4๊ฐœ๋กœ ๋‚˜๋ˆ„๊ณ  ๋˜ ๋‚˜๋ˆ„๊ณ ... => ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๊ตฌํ˜„ํ•˜์ž

 

 

๐Ÿšฉ ์‹œํ–‰์ฐฉ์˜ค

๋‚œ ์žฌ๊ท€ํ•จ์ˆ˜์— ๋งค์šฐ ์•ฝํ•˜๋‹ค... ๋ฉ์ฒญ์ด์•ผ..... ใ… ใ… ใ… ใ… 

 

์ฒ˜์Œ์—” ์•„๋ž˜์™€ ๊ฐ™์ด ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ–ˆ๊ณ , ์ด ๋•Œ ์ถœ๋ ฅ์ดˆ๊ณผ๊ฐ€ ๋‚˜์™”๋‹ค.

void check(int sx, int sy, int n) {
    int def = m[sx][sy];
    for (int i = sx; i < sx + n; i++) {
        for (int j = sy; j < sy + n; j++) {
            if (def != m[i][j]) {
                cout << "(";
                check(sx, sy, n / 2);
                check(sx + n / 2, sy, n / 2);
                check(sx, sy + n / 2, n / 2);
                check(sx + n / 2, sy + n / 2, n / 2);
                cout << ")";
            }
        }
    }
    cout << def;
}

๊ทธ ์ด์œ ๋Š” ")"์„ ์ถœ๋ ฅํ•˜๊ณ  ๋‚˜๋ฉด ๊ทธ ํ•จ์ˆ˜๋Š” ์ข…๋ฃŒ๋˜์–ด์•ผ ํ•˜๋Š”๋ฐ ์ง€๊ธˆ์€ ๊ณ„์† for๋ฌธ์„ ๋ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๋˜‘๊ฐ™์€ ์ถœ๋ ฅ์ด ๋ช‡๋ฒˆ์”ฉ ๋ฐ˜๋ณต๋œ๋‹ค. ๋”ฐ๋ผ์„œ ")"์„ ์ถœ๋ ฅํ•˜๊ณ  ํ•จ์ˆ˜๋ฅผ ์ข…๋ฃŒ์‹œํ‚ค๋Š” ์ฝ”๋“œ๋ฅผ ์ถ”๊ฐ€ํ–ˆ๋‹ค.

int check(int sx, int sy, int n) {
    int def = m[sx][sy];
    for (int i = sx; i < sx + n; i++) {
        for (int j = sy; j < sy + n; j++) {
            if (n == 1) {
                cout << def;
                return 1;
            }
            if (def != m[i][j]) {
                cout << "(";
                check(sx, sy, n / 2);
                check(sx, sy + n / 2, n / 2);
                check(sx + n / 2, sy, n / 2);
                check(sx + n / 2, sy + n / 2, n / 2);
                cout << ")";
                return 1;
            }
        }
    }
    cout << def;
}

๊ทธ๋ž˜์„œ ์œ„์™€ ๊ฐ™์ด ์ˆ˜์ •ํ–ˆ๋‹ค. ๋ฐ˜ํ™˜ํ˜•์ด void๋ฉด ๋ญ˜ ๋ฐ˜ํ™˜ํ•ด์•ผํ• ์ง€ ๋ชจ๋ฅด๊ฒ ์–ด์„œ int๋กœ ๋ฐ”๊พธ๊ณ  return 1๋กœ ํ–ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด์ œ ๋ฐœ๊ฒฌํ•œ ์‚ฌ์‹ค์ธ๋ฐ n==1 ์ € ๋ถ€๋ถ„ ํ•„์š”๊ฐ€ ์—†๋‹ค. ์–ด์งœํ”ผ 1/2=0์ด ๋˜๋‹ˆ๊นŒ ์•Œ์•„์„œ ์ข…๋ฃŒ๋œ๋‹ค.

 

๊ณ„์† ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค๊ฐ€ ๋‚˜์™€์„œ ๋„˜ ๋‹ต๋‹ตํ•ด์„œ ์ง์ ‘ ์ฐ์–ด๋ดค๋‹ค.. ๋ฐ˜๋ก€ ๊ฑฐ์˜ ๋‹ค ๋„ฃ์–ด๋ดค๋Š”๋ฐ ๋‹ค ๋งž๊ฒŒ ์ถœ๋ ฅ๋˜์—ˆ์ง€๋งŒ ์ฑ„์  ๊ฒฐ๊ณผ๋Š” ์—ฌ์ „ํžˆ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค.. ํฌ๊ธฐํ•˜๋ ค๋‹ค ํ˜น์‹œ๋‚˜ ํ•ด์„œ ๋ฐ˜ํ™˜ํ˜•์„ void๋กœ ๋ฐ”๊พธ๊ณ  return 1;์„ return;์œผ๋กœ ๋ฐ”๊ฟจ๋”๋‹ˆ ๋งž์•˜๋‹ค.. ์‚ฌ์‹ค return 1์„ ํ•œ๋‹ค๊ณ  ํ”„๋กœ๊ทธ๋žจ ๋™์ž‘์— ์˜ํ–ฅ์„ ์ฃผ์ง„ ์•Š๋Š”๋ฐ ์ฑ„์  ์‹œ์Šคํ…œ ๋‚ด๋ถ€์˜ ์‚ฌ์ •์€ ์•Œ ์ˆ˜ ์—†์œผ๋‹ˆ.. ์ž˜ ๋ชจ๋ฅด๊ฒ ๋‹ค. ์ด๊ฑฐ ๋•Œ๋ฌธ์— ํ•œ ์‹œ๊ฐ„๋™์•ˆ ์‚ฝ์งˆํ–ˆ๋‹ค.

void check(int sx, int sy, int n) {
    int def = m[sx][sy];
    for (int i = sx; i < sx + n; i++) {
        for (int j = sy; j < sy + n; j++) {
            if (n == 1) {
                cout << def;
                return;
            }
            if (def != m[i][j]) {
                cout << "(";
                check(sx, sy, n / 2);
                check(sx, sy + n / 2, n / 2);
                check(sx + n / 2, sy, n / 2);
                check(sx + n / 2, sy + n / 2, n / 2);
                cout << ")";
                return;
            }
        }
    }
    cout << def;
}

 

๊ทธ๋ฆฌ๊ณ  ์ฒ˜์Œ์— 1<=N<=64์ธ๊ฑธ ๋ณด๊ณ  ์ž…๋ ฅ์„ int๋กœ ๋ฐ›์•˜๋Š”๋ฐ, N์€ ์ž๋ฆฌ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋ฏ€๋กœ ์ •์ˆ˜ 64์ž๋ฆฌ๋Š” long long์œผ๋กœ๋„ ๋ฐ›์„ ์ˆ˜ ์—†๋‹ค. ๊ทธ๋ž˜์„œ N์˜ ์ž๋ฃŒํ˜•์„ string์œผ๋กœ ์ˆ˜์ •ํ–ˆ๋‹ค.

 

 

๐Ÿ’ป ์ฝ”๋“œ (C++)

#include <iostream>
using namespace std;

int m[65][65];

void check(int sx, int sy, int n) {
    int def = m[sx][sy];
    for (int i = sx; i < sx + n; i++) {
        for (int j = sy; j < sy + n; j++) {
            /* ์—†์–ด๋„ ๋จ
            if (n == 1) {
                cout << def;
                return;
            } */
            if (def != m[i][j]) {
                cout << "(";
                check(sx, sy, n / 2);
                check(sx, sy + n / 2, n / 2);
                check(sx + n / 2, sy, n / 2);
                check(sx + n / 2, sy + n / 2, n / 2);
                cout << ")";
                return;
            }
        }
    }
    cout << def;
}

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

    int N;
    string x;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> x;
        for (int j = 0; j < N; j++) {
            m[i][j] = x[j]-'0';
        }
    }
    
    check(0, 0, N);
}

'๐Ÿ’ป Algorithms > ๋ฐฑ์ค€' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€] 1260 DFS์™€ BFS - dfs, bfs  (0) 2024.08.20
[๋ฐฑ์ค€] 2164 ์นด๋“œ2 - ํ  (0) 2024.08.19
[๋ฐฑ์ค€] 11403 ๊ฒฝ๋กœ ์ฐพ๊ธฐ - ๊ทธ๋ž˜ํ”„, DFS  (0) 2024.08.17
[๋ฐฑ์ค€] 1927 ์ตœ์†Œ ํž™ - ์šฐ์„ ์ˆœ์œ„ ํ  (0) 2024.08.14
[๋ฐฑ์ค€] 11780 ํ”Œ๋กœ์ด๋“œ2 - ํ”Œ๋กœ์ด๋“œ ๊ฒฝ๋กœ๋ณต์›  (0) 2024.08.04
'๐Ÿ’ป Algorithms/๋ฐฑ์ค€' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€] 1260 DFS์™€ BFS - dfs, bfs
  • [๋ฐฑ์ค€] 2164 ์นด๋“œ2 - ํ
  • [๋ฐฑ์ค€] 11403 ๊ฒฝ๋กœ ์ฐพ๊ธฐ - ๊ทธ๋ž˜ํ”„, DFS
  • [๋ฐฑ์ค€] 1927 ์ตœ์†Œ ํž™ - ์šฐ์„ ์ˆœ์œ„ ํ
์ ๋„
์ ๋„
  • ์ ๋„
    ๋„์ 
    ์ ๋„
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (30)
      • ๐Ÿ’ป Algorithms (28)
        • ๋ฐฑ์ค€ (22)
        • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (6)
      • ๐Ÿ”Ž Deep Learning (0)
      • ๐Ÿ’ฅ ํŠธ๋Ÿฌ๋ธ”์ŠˆํŒ… (1)
      • ๐Ÿ•น Unity (1)
      • ๐Ÿฅ” ์ž‰ํ…… (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

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

    • Blog
    • Github
    • Velog
  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
์ ๋„
[๋ฐฑ์ค€] 1992 ์ฟผ๋“œํŠธ๋ฆฌ - ์žฌ๊ท€ํ•จ์ˆ˜
์ƒ๋‹จ์œผ๋กœ

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