[알고리즘 문제해결 전략]6장. 무식하게 풀기_②

BOGGLE in algospot

---

problem

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOGGLE
  • 10000ms
  • 65536kb
  • 10129
  • 1635 (16%)

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

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

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

주의: 알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 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

Thinking

 처음 문제를 접했을 때 교제의 단원의 제목 그대로 완전탐색을 하여 문제를 풀고자 시도하였다. 하지만 위에 문제에서 경고를 적어 놓은 것을 확인한 후 실행시간에 대해 적어 보았다. 최대 50개의 테스트 케이스가 주어지며 시간 제한이 10초인것에 초점을 맞추어 보았다. 한번의 케이스가 최대 2초이내에 실행이 되어야한다. 그리고 하나의 단어를 찾는 데에는 0.2초이내에 존재여부를 판별할 수 있어야한다. 단어의 길이가 10일때 최대 의 탐색시간을 가지게 되므로 시간 초과가 발생하게 된다. 

 자, 그렇다면 어떤식으로 문제를 해결해야 할까?

 해당 문제를 해결하기 위해서 8장의 '동적 계획법'에서 배우는 메모이제이션 기법을 사용하였다. 알고리즘은 다음과 같다.

 먼저 각각의 보드에 대한 정보를 저장해놓을 score와 임시적으로 점수를 계산할 tmp_score라고 하는 정수형 매트릭스를 보드와 동일한 크기로 생성하고 0으로 초기화를 시키고 생각을 해보자.

 

 각 문자열의 문자마다 보드판을 순회하며 체크를 하자. 단 아래의 규칙으로 tmp_score의 점수를 올리자.

1. [j , k]의 보드판에서 문자열의 i번째 인덱스의 문자(이하 strings[i])와 동일할때, 해당 지점에서 주변의 score점수와 이때까지 검사한 문자열의 길이 즉, i+1 와 max(score[i][j]) + 1의 값 중 더 작은 값을 tmp_score[i][j]의 값으로 채택한다.

2. 1의 과정을 모든 모드판의 칸에서 다 마치고 난 후, score판에  tmp_score의 값들을 copy한다.

3. 1,2의 과정을 문자열의 마지막 까지 마친다.

4. score의 값들 중 문자열의 길이보다 큰 값이 있으면 해당 문자열은 보드판에서 만들 수 있다.

**그림으로 이해해보자.

 

 

i = 0일때,  strings[i] = 'P' 이고 보드판에 'P'의 문자를 가지는 칸은 [0,3],[1,1]이므로 해당 위치에서 min(i + 1 , max(score[i][j]) + 1)의 값을 구하여 tmp_score[i][j]에 대입해 준다. 여기서, 더 작은 값을 채택하는 이유는 검사하는 문자열의 길이보다 score의 점수가 더 큰 모순이 발생하지 않도록 하기 위해서이다. 

i = 1일때,  strings[i] = 'R' 이고 보드판에 'R'의 문자를 가지는 칸은 [0,1],[1,2],[4,3]이다.

i = 2일때,  strings[i] = 'E' 이고 보드판에 'E'의 문자를 가지는 칸은 [1,3],[2,3]이다.

i = 3일때,  strings[i] = 'T' 이고 보드판에 'T'의 문자를 가지는 칸은 [1,4],[2,4],[3,1]이다.

i = 4일때,  strings[i] = 'T' 이고 보드판에 'T'의 문자를 가지는 칸은 [1,4],[2,4],[3,1]이다.

i = 5일때,  strings[i] = 'Y' 이고 보드판에 'T'의 문자를 가지는 칸은 [3,4]이다.

해당 예제에서는 6이상인 점수가 score판에 마지막에 존재하게 되므로 YES가 반환된다.

**하나의 문자의 탐색이 끝날 때마다 tmp_score값을 score에 옮기는 이유:

위에 주어진 예제를 가지고 고민을 해보아라.

위의 알고리즘에서는 10*5*5*8 = 2000의 반복이 하나의  문자열당 생긴다. 2000번의 경우 0.2초안에 처리가 충분하다.

Solve

성공 코드  && TLE 코드 << 각각 click

출처

---

문제:  algosport BOGGLE문제( 링크 )

예외 상황 : algospot BOGGLE문제 댓글