Hibbah   9년 전

최대 30만개의 단어목록과 4X4크기의 보드가 주어졌을때,

보드에서 인접한 8방향으로 알파벳을 이어붙여 만든 단어가 처음에 주어진 단어목록에 있는지 찾는 문제입니다. (단어의 최대 길이 = 8)

모든 단어는 알파벳 대문자로만 구성되므로, 30만개의 단어들을 27진수의 정수로 바꿔 표현한 뒤 단어 목록을 정렬해두고,

(26진수로 표현했을 경우, 'A'의 가중치가 0이 되어 "APPLE", "PPLE"와 같은 단어를 동일한 단어로 취급하게 되므로 27진수로 표현했습니다.)

4X4 보드에서 가능한 모든 단어들을 만들어가면서 정렬된 단어목록에서 이진탐색을 하는 방식으로 구현했습니다.

(4X4 보드에서 8방향으로 탐색하면서 길이 8이하인 단어를 만드는 모든 경우의수를 확인해보니 28만개가 나왔습니다. 단순히 8^8(1600만)이라고 대충 생각한것보다 실제로 확인해보니 엄청 차이나네요...)

Search함수 내에서

1. (x,y)의 알파벳을 이어붙임 (target에 27진수로 누적해서 표현)

2. 현재까지 이어붙여 만든 단어를 이미 예전에 단어목록에서 찾은경우가 있는지 set<longlong>cache에서 확인

3. 현재까지 만든 단어가 단어목록에 존재하는 단어인지 이진탐색

4. 길이가 8미만인 경우에만 8방향으로 완전탐색

의 순서로 탐색을 진행하도록 구현했습니다.

(한 단어를 만드는데 보드에서 동일한 위치의 알파벳을 사용할 수 없으므로, visit[][]배열을 사용하여 알파벳의 사용 여부를 체크했습니다.)

찾은 단어들 중에 가장 긴 단어를 출력해야 하므로, class Word의 operator <를 통해서 단어를 찾을때마다 가장 긴 단어(길이가 같은 경우에는 사전순)를 갱신하도록 하였습니다.



소스가 굉장히 길어 자세하게 설명하려고 했는데 충분한지 모르겠네요.......

고통받는 저를 위해 도와주실 천사님을 모십니다......

도와주십셔 (_ _)

amugeona   9년 전

length가 3 이하인 경우를 찾게 되더라도 count는 증가해야됩니다.

이때 점수는 0점입니다.

Hibbah   9년 전

그런 엄청난 사실이................

수정해서 제출해보니 시간초과긴 하지만 그래도 쬐끔 해소되어 다행이네요

고맙습니다 ㅎㅎ

Hibbah   9년 전

0ea3ae106141331a8622ea38926e215f.jpg


와우!! 덕분에 완쾌되었네요

고맙습니다ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.