[ ๋ฌธ์ ๋งํฌ ]
https://www.acmicpc.net/problem/1992
๐ฉ ์กฐ๊ฑด
- 0,1๋ก๋ง ๊ตฌ์ฑ๋ ์์์ ์์ถํด๋ผ. ๋ชจ๋ 0์ผ๋ก๋ง ๋์ด ์์ผ๋ฉด ์์ถ ๊ฒฐ๊ณผ๋ "0". ๋ชจ๋ 1๋ก๋ง ๋์ด ์์ผ๋ฉด ์์ถ ๊ฒฐ๊ณผ๋ "1".
- ์์ฌ ์์ผ๋ฉด ์ผ์ชฝ ์, ์ค๋ฅธ์ชฝ ์, ์ผ์ชฝ ์๋, ์ค๋ฅธ์ชฝ ์๋, ์ด๋ ๊ฒ 4๊ฐ์ ์์์ผ๋ก ๋๋์ด ์์ถํ๊ณ , ๊ฒฐ๊ณผ๋ฅผ ์ฐจ๋ก๋๋ก ๊ดํธ ์์ ๋ฌถ์ด์ ํํ
- NxN ํฌ๊ธฐ์ ์์์ด ์ฃผ์ด์ง๊ณ , 1<=N<=64
๐ฉ ์ ๊ทผ
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 |