BOGGLEGAME_알고리즘_2

2. 배열에 표시하기

생각

1단계. 25 x 25의 배열 선언

2단계. 각 원소에 인접함의 유무를 저장함

ex) 4 x 4 일때

A  A  A  S     ->        0   1   2   3

A  E  E  A     ->        4   5   6   7

A  Y  E  A     ->        8   9  10  11

A  A  A  A     ->       12  13  14 15

이면 

arr[15][15] = 

    0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15

0      1          4  5 

1  0      2      4  5  6

2      1      3      5  6  7

3          2              6  7

4  0  1              5          8  9

5  0  1  2      4      6      8  9  10

6      1  2  3      5      7      9  10  11

7          2  3          6              10  11

8                  4  5              9              12  13

9                  4  5  6      8      10        12  13  14

10                    5  6  7      9        11        13  14  15

11                        6  7          10                    14  15

12                                8  9                    13

13                                8  9  10        12        14

14                                    9  10  11        13        15

15                                        10  11              14

3단계. 찾고자하는 문자열을 위의 인덱스로 변환후 저장한다.

ex) YES -> 9 6 3

      YEA -> 9 10 11

4단계. 저장한 숫자 배열(편의상 YES배열 )을 순회하며 arr[ i ][ i+1 ]에 YES의 (i+1)번째 요소가 들어있는지 검사한다.  있으면 i++ 후 i가 숫자 배열의 끝일때까지 반복

ex) YES -> ( arr[YES[i] ][ YES[i+1] ] == 6) 

문제

처음 위 알고리즘을 생각했을땐 2차원 배열을 가장먼저 만들어 놓기만 하면 모든 답을 처리할수 있기에 시간적인 문제를 해결할 수 있을 것이라 생각했다. 때문에 정답이라고 생각했는데 다음과 같은 경우에 답을 찾지 못하는 문제가 있다.

A  A  A  A     ->        0   1   2   3

A  E  E  E     ->        4   5   6   7

A  Y  A  A     ->        8   9  10  11

A  A  A  A     ->       12  13  14 15

일때  E E E Y의 경우 숫자배열에 5 6 5 9 로 저장되어야 함이 맞다. 하지만 위의 알고리즘은 숫자 배열을 만들때 

8방향 탐색을 하지 않는다. 때문에 7의 E를 저장하고 다음 요소인 Y를 찾을 수 없어 오답처리된다.

다른 방법을 찾아야겠다.