Computer Language/Algorithm
백준 알고리즘 C# 1992 쿼드트리 - MJ
유민재
2021. 11. 10. 23:50
728x90
문제
https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
Code
|
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
|
using System;
using System.Linq;
using System.Collections.Generic;
namespace PracticeAlgo
{
class Program
{
static int N;
static void Main(string[] args)
{
using (var prnt = new System.IO.StreamWriter(Console.OpenStandardOutput()))
{
N =int.Parse( Console.ReadLine());
char[,] origin = new char[N, N];
for (int j = 0; j < N; j++)
{
for(int i=0; i < N; i++)
{
origin[i, j] = Convert.ToChar(Console.Read());
}
Console.ReadLine();
}
string S = searchTree(origin);
prnt.WriteLine(S);
}
}
static string searchTree(char[,] tree)
{
string rtn = "(";
if (Searchdiffrent(tree))
{
return tree[0, 0].ToString() ;
}
if (tree.Length == 4)
{
for (int j = 0; j < 2; j++)
{
for (int i = 0; i < 2;i++)
{
rtn += tree[i, j].ToString();
}
}
return rtn + ")";
}
else
{
var length = Convert.ToInt32(Math.Sqrt(tree.Length)) / 2;
var buf1 = new char[length, length];
var buf2 = new char[length, length];
var buf3 = new char[length, length];
var buf4 = new char[length, length];
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
buf1[i, j] = tree[i, j];
buf2[i, j] = tree[length + i, j];
buf3[i, j] = tree[i, length + j];
buf4[i, j] = tree[length + i, length + j];
}
}
return rtn+ searchTree(buf1) + searchTree(buf2) + searchTree(buf3) + searchTree(buf4) + ")";
}
}
static bool Searchdiffrent(char[,] tree)
{
char x = tree[0, 0];
var length = Convert.ToInt32(Math.Sqrt(tree.Length)) ;
bool rtn = true;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
rtn = (tree[i, j] == x);
if (!rtn)
{
return rtn;
}
}
}
return rtn;
}
}
}
|
cs |
생각
1. 음.. 내가 보기 편한 배열 형식에 저장하자. 수학적인 배열의 형태를 가지고 있는 것이 편하기 때문에 Console.Read()
를 통해 하나씩 받고 한줄 크기를 받으면 Console.ReadLine(); 을 통해 줄넘겨 배열을 완성하자.
2. 함수에서는 제시된 기저( 배열이 한가지 숫자이면 한 숫자로 표현, 가장 작은 배열크기 2X2에서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 차례대로 표시하고 )로 닫는다.
3. 만약 기저에 포함되지 않는 경우 4개의 buffer를 만들어 재기를 통해 기저 조건을 향해 보낸다.
이론
분할 정복, 재귀
반응형