백준 1013번, Contact
백준 1013번 c언어 문제 풀이
문제:
푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.
이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.
전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ ( ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.
(xyx)+ ( ) 는 괄호 내의 xyx의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.
1+ = { 1, 11, 111, 1111, 11111, … }
10+ = { 10, 100, 1000, 10000, 100000, … }
(01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
(1001)+ = { 1001, 10011001, 100110011001, … }
10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
(10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }
반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.
(100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }
최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.
(100+1+ | 01)+
김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.
먼저 정규표현식이 어떤 식으로 돌아가는지 확인해야된다.
| 노드0 | 노드1 | 노드2 | 노드3 | 노드 4 | 노드5 | 노드6 | 노드7 | |
|---|---|---|---|---|---|---|---|---|
| 1 | 노드1 | 노드8 | 노드8 | 노드4 | 노드5 | 노드5 | 노드0 | 노드0 |
| 0 | 노드7 | 노드2 | 노드3 | 노드3 | 노드7 | 노드6 | 노드3 | 노드8 |
위의 표는 각 노드에 0, 1이 들어갔을 때 어느 노드로 가야하는지 표현한 표이다.
노드 8은 가면 오류가나는 위치로 표시했다.
그리고 패턴이 끝나는 노드의 위치도 중요하다. 노드4, 노드5, 노드0에서 패턴이 끝나야 알맞게 패턴이 끝나는 것이다.
다른 위치에서 패턴이 끝나게 된다면 오류가 있는 패턴인 것이다.
위의 상황을 고려해 코드를 짜보겠다.
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
#include <stdio.h>
#include <string.h>
int main(){
char arr[200];
int start;
int length;
scanf("%d",&start);
for(int i=0; i<start; i++){
scanf("%s",&arr); //패턴 입력하기
length = strlen(arr); //패턴 길이
int count = 0;
int node = 0; // 노드는 0부터 시작
while(1){
if(count == length){
if(node == 4 || node == 5 || node == 0){
printf("YES\n");
break;
}else{
printf("NO\n");
break;
}
}
if(node == 0){ //노드 0일때
if(arr[count] == '0'){ //전파의 신호가 0이면
node = 7;
}
else if(arr[count]== '1'){
node = 1;
}
}
else if(node == 1){
if(arr[count] == '0'){
node = 2;
}
else if(arr[count] == '1'){
node = 8;
}
}
else if(node == 2){
if(arr[count] == '0'){
node = 3;
}
else if(arr[count] == '1'){
node = 8;
}
}
else if(node == 3){
if(arr[count] == '0'){
node = 3;
}
else if(arr[count] == '1'){
node = 4;
}
}
else if(node == 4){
if(arr[count] == '0'){
node = 7;
}
else if(arr[count] == '1'){
node = 5;
}
}
else if(node == 5){
if(arr[count] == '0'){
node = 6;
}
else if(arr[count] == '1'){
node = 5;
}
}
else if(node == 6){
if(arr[count] == '0'){
node = 3;
}
else if(arr[count] == '1'){
node = 0;
}
}
else if(node == 7){
if(arr[count] == '0'){
node = 8;
}
else if(arr[count] == '1'){
node = 0;
}
}
else if(node == 8){
printf("NO\n");
break;
}
count++; //다음 신호
}
}
return 0;
}
조건에 맞게 if문을 돌려 결과를 출력하였습니다.