1. 무식하게 풀기


생각

1단계. 먼저 5 x 5 배열에 문자열을 입력받는다.

2단계. 그후 검사할 문자열들을 N개 입력 받는다.

3단계. 입력받은 각 문자열의 문자들이 서로 인접하고 있는지를 판단하는 함수를 호출 true면 YES, false면 NO 출력

함수 내용 

 - bool f(int x,  int y,  char curCharacter) 

 - x 또는 y가 범위 0 <= (x, y) < 5 가 아니라면 false

 - 배열의 [y][x] 인덱스에 있는 문자가 찾아야 할 문자가 아니면 false

 - 해당 인덱스의 문자가 찾는 문자이고 문자열의 길이가 1이라면 true

 - 해당 인덱스의 문자가 찾는 문자이고 문자열의 길이가 1이 아니라면 다음 문자를 인접하는 8방향의 x, y와 다음 문자를 인자로 f함수 재귀 호출

 - 찾는 문자가 문자열의 마지막 문자이면 모두 찾은 것이므로 true


코드

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// BOGGLEGAME_1
#include <iostream>
#include <string.h>
static const int BOGGLE_MAX = 5;
static const int WORD_MAX = 10;
int g_ArrX[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int g_ArrY[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
char* g_Boggle[BOGGLE_MAX];
char* g_WordsArr[WORD_MAX];
int g_StringLen = 0;
int g_CurCharNum = 0;
int g_CurWordNum = 0;
 
// 해당 좌표에 전달되는 문자가 있는지 검사
bool f(int y, int x, char CurChar)
{
    // 기저사례 1 x또는 y가 범위 밖이라면 false
    if (x < 0 || y < 0)     
        return false;
    // 기저사례 1 x또는 y가 범위 밖이라면 false
    if (x >= BOGGLE_MAX || y >= BOGGLE_MAX)     
        return false;
    // 기저사례 2 찾으려는 문자가 '\0' 이거나
    // 문자열의 길이와 같으면 문자열을 찾은것이므로 true
    if (CurChar == '\0' || g_CurCharNum > g_StringLen)      
        return true;
                                             
    if (g_Boggle[y][x] == CurChar)
    {
        if (g_StringLen == 1){
            // 기저사례 3 문자를 찾았는데 문자열의 
            // 길이가 1이면 곧 찾는 문자열이므로 true
            return true;
        }
 
        // 문자를 찾았으면 문자인덱스를 1증가
        ++g_CurCharNum;   
 
        // 현 인덱스를 중심으로 다음 문자를 8방향 검사
        for (int i = 0; i < 8; i++)
        {
            // 모두 찾으면 true
            if (f(
                (y + g_ArrY[i]), // y좌표
                (x + g_ArrX[i]), // x좌표
                g_WordsArr[g_CurWordNum][g_CurCharNum])
                )
            {
                return true;       
            }
        }
        // 문자를 못찾았으면 문자인덱스 1감소
        --g_CurCharNum;      
    }
    // 현 인덱스의 문자가 찾는 문자가 아니면 false
    return false;       
}
 
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    int stringCount = 0;
    int temp = 0;
    for (int i = 0; i < BOGGLE_MAX; i++)
    {
        g_Boggle[i] = new char[BOGGLE_MAX + 1]();
    }
    for (int i = 0; i < WORD_MAX; i++)
    {
        g_WordsArr[i] = new char[WORD_MAX + 1]();
    }
 
    scanf("%d", &testCase);
    while (testCase--){
        g_CurWordNum = 0;
        
        // 보글게임판 5 x 5 입력
        for (int i = 0; i < BOGGLE_MAX; i++)     
        {
            scanf("%s", g_Boggle[i]);
        }
 
        // 확인하려는 문자열 갯수 입력
        scanf("%d", &stringCount);
        temp = stringCount;
        // 확인하려는 문자열 입력  ENTER 구분
        for (int i = 0; i < stringCount; i++)
           {
            scanf("%s", g_WordsArr[i]);
        }
 
        while (stringCount--){
            bool isYes = false;
            // 현재 검사하려고 하는 문자열의 길이 저장
            g_StringLen = (int)strlen((const char*)g_WordsArr[g_CurWordNum]);
            // g_CurCharNum = 현재 검사하려고하는 문자 인덱스 예) ABCDE에서 C 면 2    
            g_CurCharNum = 0;               
 
            for (int y = 0; y < BOGGLE_MAX; y++)
            {
                for (int x = 0; x < BOGGLE_MAX; x++)
                {
                    // y, x인덱스와 찾으려는 문자열의 문자를 f에 넘김
                    // 있으면 YES
                    if (
                        f(y,
                          x, 
                          g_WordsArr[g_CurWordNum][g_CurCharNum]))     
                    {
                        printf("%s YES\n", g_WordsArr[g_CurWordNum++]);
                        isYes = true;      // 루프를 빠져나간다.
                        break;              // 루프를 빠져나간다.
                    }
                }
                if (isYes)              // 루프를 빠져나간다..
                break;                      // 루프를 빠져나간다..
            }
            
            // 4, 4까지 돌았는데 없으면 NO    
            if (!isYes)     
            {
                printf("%s NO\n", g_WordsArr[g_CurWordNum++]);
            }
        }
    }
    
    // 메모리 해제
    for (int i = 0; i < BOGGLE_MAX; i++)        
    {
        delete []g_Boggle[i];
        g_Boggle[i] = NULL;
    }
    for (int i = 0; i < WORD_MAX; i++)
    {
        delete[]g_WordsArr[i];
        g_WordsArr[i] = NULL;
    }
    return 0;
}
cs

결과

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
1
KKKKS
KEEEK
KEYEK
KEEEK
KKKKK
10
YES
YESYES
SYESEY
YESSEY
SYESKSYEY
YESKK
SYESKKY
YESKEY
YESEEY
YESEEEEEEEY
YES YES
YESYES NO
SYESEY NO
YESSEY NO
SYESKSYEY NO
YESKK YES
SYESKKY NO
YESKEY YES
YESEEY YES
YESEEEEEEEY YES
cs


위 방법으로 구하면 최대 

50(최대 테스트 케이스) * 10(문자열의 개수)  * 8^10 (8방향으로 검사하는 것을 글자수만큼 반복 최대 10)

대략 5000억 정도..어마어마하다. 당연 시간초과

이것을 어떻게 줄일 수 있을까.

'All > Algorithm' 카테고리의 다른 글

BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28
BOGGLEGAME_문제  (0) 2015.12.28
ZEROONE_알고리즘  (0) 2015.12.28
ZEROONE_문제  (0) 2015.12.28

이번에 푼 문제는 BOGGLEGAME 이다.

아래와 같다.


문제

 

보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.

예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.

보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.

 

입력

 

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.
그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

 

출력

 

각 테스트 케이스마다 N줄을 출력합니다. 각 줄에는 알고 있는 단어를 입력에 주어진 순서대로 출력하고, 해당 단어를 찾을 수 있을 경우 YES, 아닐 경우 NO를 출력합니다.

 

예제 입력

1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX

예제 출력

PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES


요약하면

1. 5 x 5의 배열에 문자열 입력 

2. 그후 길이가 10이하인 문자열 N개 입력

3. 5 x 5의 배열의 한 원소에서 시작해서 인접하는 원소들을 연결하여 문자열이 존재하는지 확인 존재하면 YES 아니면 NO 

4. 연결할때 사용했던 문자를 다시 사용할 수 는 있지만 한 문자를 연속해서 계속 사용할 수는 없다.

조건 테스트케이스는 50이며 10000ms안에 수행되어야한다. 

*문제 출저 알고스팟

'All > Algorithm' 카테고리의 다른 글

BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28
BOGGLEGAME_알고리즘_1  (0) 2015.12.28
ZEROONE_알고리즘  (0) 2015.12.28
ZEROONE_문제  (0) 2015.12.28

1. 무식하게 풀기


생각

1단계. 먼저 0, 1로 이루어진 수열을 배열에 입력받는다.

2단계. 두개의 인덱스A, B를 입력받는다.

3단계. 함수 bool f(int A, int B)를 호출

함수 내용 

- 배열의 A번째부터 B까지 순차적으로 비교

- 비교 중 A번째 인덱스에 들어있는 값과 다르면 false 리턴


코드

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
#include <iostream>
// 백만
static const int MAX = 1000000;
char g_ZeroOneArr[MAX + 1] = {0, };
bool f(int indexA, int indexB);
 
int main(void)
{
    // 입력되는 두 수
    int indexA, indexB = 0;
    // 테스트 케이스
    int testCase = 0;
    scanf("%s", g_ZeroOneArr);
    scanf("%d", &testCase);
    
    while(testCase--){
        // 두 수 입력
        scanf("%d %d", &indexA, &indexB);
 
        // 오름차순 정렬
        if(indexA > indexB)
        {
            int temp = indexA;
            indexA = indexB;
            indexB = temp;
        }
        
        // (모두 1 or 모두 0) == YES
        if(f(indexA, indexB))
            printf("Yes\n");
        else
            printf("No\n");
    }
}
// 함수 구현
// 인덱스 A ~ B까지 반복 하며 중간에 값이 변하면 FALSE
bool f(int indexA, int indexB)
{
    for(int i = indexA; i <= indexB; i++)
    {
        if(g_ZeroOneArr[i] != g_ZeroOneArr[indexA])
        {
            return false;
        }
    }
    return true;
}
 
 
cs
 

출력

1
2
3
4
5
6
7
8
9
10
11
12
13
1111100000
 
5
1 0
Yes
1 1
Yes
4 5
No
5 4
No
0 9
No
cs


위와같이 출력되는것을 알수 있다. 

하지만 위의 코드를 문제 풀이 사이트에 제출하면 [TimeOut] 이 되어버린다.


좀더 빠른 코드를 짜야한다.

먼저 위의 코드는 아래와 같은 최악의 경우


0000000....1(N = 100만)

indexA = 0, indexB = 999999

테스트 케이스 10만


100만 * 10만 의 for문을 반복한다.


2. 배열에 기록하기


생각

1단계. 먼저 0, 1로 이루어진 수열을 배열에 입력받는다.

2단계. 배열을 0 ~ N 까지 반복하면서 i값을 기록한다. (i는 0부터 시작)

          - if( arr[N] != arr[N -1] ) 라면 i 값을 1더하여 기록

3단계. 함수 bool f(int A, int B)를 호출

함수 내용 

- 배열의 A번째 원소와 B번째 원소의 값이 서로 다르면 false 같으면 true 반환


코드


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
// ZEROONE_2
#include <iostream>
 
// 백만
static const int MAX = 1000000;
// 수열 배열
char g_ZeroOneArr[MAX + 1] = {0, };
// 기록 배열
int g_CheckFlagArr[MAX + 1] = {0, };
bool f(int indexA, int indexB);
 
int main(void)
{
    // 입력되는 두 수
    int indexA, indexB = 0;
    // 테스트 케이스
    int testCase = 0;
    // 수열의 길이
    unsigned long stringLength = 0;
    unsigned int checkFlag = 0;
    
    scanf("%s", g_ZeroOneArr);
    scanf("%d", &testCase);
    stringLength = strlen(g_ZeroOneArr);
    
    // 체크 플래그 설정
    // i번째 요소와 i-1번째 요소가 서로 다르면 check + 1
    for(int i = 1 ;i < stringLength; i++)
    {
        if(g_ZeroOneArr[i-1] != g_ZeroOneArr[i])
            checkFlag++;
        g_CheckFlagArr[i] = checkFlag;
    }
    
    while(testCase--){
        // 두 수 입력
        scanf("%d %d", &indexA, &indexB);
        
        // (모두 1 or 모두 0) == YES
        if(f(indexA, indexB))
            printf("Yes\n");
        else
            printf("No\n");
    }
}
cs


출력

1
2
3
4
5
6
7
8
9
10
11
12
1010101100
5
1 2
No
2 1
No
1 1 
Yes
2 4
No
4 5
No
cs


딱히 어려운 부분은 없으므로 설명은 생략하고 for문 횟수를 보면 

처음에 최대 100만번을 반복하고 그후에는 반복이 없는 것을 알수 있다.

즉 100만 + 10만 최대 110만 번 반복,  이전의 알고리즘보다 매우 빠른 속도를 낼 수 있다는것을 알 수 있다. 

문제풀이 사이트에 제출하니 (실행시간 241ms) 정답을 받을 수 있었다. 

'All > Algorithm' 카테고리의 다른 글

BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28
BOGGLEGAME_알고리즘_1  (0) 2015.12.28
BOGGLEGAME_문제  (0) 2015.12.28
ZEROONE_문제  (0) 2015.12.28

+ Recent posts

티스토리툴바